Submission #1322363

#TimeUsernameProblemLanguageResultExecution timeMemory
1322363behrad동기화 (JOI13_synchronization)C++20
100 / 100
180 ms21784 KiB
#ifdef LOCAL #include "/home/bgopc/template/pch.hpp" #endif #include <bits/stdc++.h> using namespace std; // * No One Dies a Virgin, Life Fucks Us All typedef long long ll; #define nl '\n' #define ff first #define ss second #define pb push_back #define sik(x) {cout << x << nl; return;} constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20; typedef pair<int, int> pii; int n, m, q, in[maxn], out[maxn], T = 1, sz[maxn], ans[maxn], lst[maxn], up[maxn][LG], fen[maxn], active[maxn]; vector<int> g[maxn]; pii E[maxn]; void dfs(int v, int p = 0) { up[v][0] = p; for (int i = 1 ; i < LG ; i ++) up[v][i] = up[up[v][i - 1]][i - 1]; in[v] = T ++; for (int u : g[v]) { if (u != p) dfs(u, v); } out[v] = T; } inline void add(int p, int x) { for (; p <= n + 1 ; p += p & -p) fen[p] += x; } inline int get(int p) { int res = 0; for (; p ; p -= p & -p) res += fen[p]; return res; } inline int root(int v) { int u = v; for (int i = LG - 1 ; i >= 0 ; i --) { if (up[u][i] && get(in[up[u][i]]) == get(in[v])) u = up[u][i]; } return u; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> q; for (int i = 1 , u ,v ; i <= n - 1 ; i ++) { cin >> u >> v; g[u].pb(v); g[v].pb(u); E[i] = {u, v}; } dfs(1); for (int i = 1 ; i <= n ; i ++) ans[i] = 1; for (int i = 1 ; i <= n - 1 ; i ++) { auto &&[u, v] = E[i]; if (v == up[u][0]) swap(u, v); add(in[v], 1); add(out[v], -1); } for (int e ; m -- ; ) { cin >> e; auto [u, v] = E[e]; if (active[e]) { ans[v] = lst[v] = ans[root(u)]; add(in[v], 1); add(out[v], -1); } else { ans[root(u)] += ans[v] - lst[v]; add(in[v], -1); add(out[v], +1); } active[e] ^= 1; } for (int v ; q -- ; ) { cin >> v; cout << ans[root(v)] << nl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...