Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51810 AK2022071332 树上博弈 C++ 运行出错 0 2 MS 2596 KB 2396 2022-07-13 14:55:19

Tests(0/20):


#include <bits/stdc++.h> #include <bits/extc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define For(i,s,t) for (int i = (s); i <= (t); ++i) #define Rof(i,s,t) for (int i = (s); i >= (t); --i) using LL = long long; using Pii = pair<int, int>; template <typename T> using Heap = __gnu_pbds::priority_queue<T, greater<T>, __gnu_pbds::pairing_heap_tag>; template <typename T> using BST = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; const int inf = 0x3f3f3f3f; const LL infLL = 0x3f3f3f3f3f3f3f3fLL; const int maxn = 100000 + 5; int n, m, k; int c[maxn]; vector<Pii> g[maxn]; int clk, in[maxn], out[maxn], a[maxn*2]; int x[maxn], y[maxn], h[maxn]; int l[maxn], r[maxn], id[maxn], ret[maxn]; bitset<maxn> bst; struct MarriageAndGamingChallenge { void dfs(int u, int p) { in[u] = ++clk, a[clk] = u; rep(i,g[u].size()) { int v = g[u][i].first, w = g[u][i].second; if (v == p) continue; c[v] = w; dfs(v, u); } out[u] = ++clk, a[clk] = u; } void solve() { clk = 0; dfs(1, 0); rep(i,m) { int u = x[i], v = y[i]; if (in[u] > in[v]) swap(u, v); l[i] = (out[u] >= out[v]? in[u] + 1: out[u]), r[i] = in[v], id[i] = i; } k = sqrt(n); sort(id, id + m, [&](int i, int j) { return l[i] / k != l[j] / k? l[i] < l[j]: l[i] / k % 2? r[i] < r[j]: r[i] > r[j]; }); bst.reset(); bst.set(n + 1); int s = 1, t = 0; for (int j = 0; j < m; ++j) { int i = id[j]; while (s > l[i]) bst.flip(n - c[a[--s]]); while (t < r[i]) bst.flip(n - c[a[++t]]); while (s < l[i]) bst.flip(n - c[a[s++]]); while (t > r[i]) bst.flip(n - c[a[t--]]); h[i] = n - h[i]; ret[i] = bst._Find_next(h[i] - 1) - h[i]; } } }; int main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); scanf("%d", &n); For(i,1,n) g[i].clear(); rep(i,n-1) { int u, v, w; scanf("%d%d%d", &u, &v, &w), --w; g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w)); } scanf("%d", &m); rep(i,m) scanf("%d%d%d", &x[i], &y[i], &h[i]), --h[i]; (new MarriageAndGamingChallenge())->solve(); rep(i,m) printf("%d\n", ret[i]); return 0; }


测评信息: