제출 #1184752

#제출 시각아이디문제언어결과실행 시간메모리
1184752tin_leSynchronization (JOI13_synchronization)C++20
30 / 100
252 ms57652 KiB
#include <bits/stdc++.h> using namespace std; // shorthand using ll = long long; using pii = pair<int,int>; using vi = vector<int>; using vvi = vector<vi>; using vpii = vector<pii>; template<class T> using vt = vector<T>; // ------------------- FW (Fenwick Tree) for 1-indexed arrays ----------------------- template<class T, typename F = function<T(const T&, const T&)>> class FW { public: int n, N; vt<T> tree; T DEFAULT; F func; FW() {} // n here is the maximum valid index (1-indexed), so we create tree[1..n] FW(int n, T DEFAULT, F func) : func(func) { this->n = n; this->DEFAULT = DEFAULT; // we'll allocate vector of size n+1 so that indices 1..n are used. tree.resize(n + 1, DEFAULT); N = floor(log2(n)) + 1; // for select, if needed. } // update_at: add val at index id (id between 1 and n) void update_at(int id, T val) { assert(id >= 1); for(; id <= n; id += id & -id) tree[id] = func(tree[id], val); } // get: prefix sum from 1 to id. T get(int id) { assert(id >= 1 && id <= n); T res = DEFAULT; for(; id; id -= id & -id) res = func(res, tree[id]); return res; } // queries_range: sum in [l, r] (1-indexed) T queries_range(int l, int r) { if(l > r) return DEFAULT; return get(r) - (l > 1 ? get(l - 1) : 0); } T queries_at(int i) { return queries_range(i, i); } // update_range: add val to each index in [l, r] void update_range(int l, int r, T val) { update_at(l, val); if(r + 1 <= n) update_at(r + 1, -val); } void reset() { tree.assign(n + 1, DEFAULT); } int select(int x) { // get pos where prefix sum >= x int global = get(n), curr = 0; for(int i = N; i >= 0; i--) { int t = curr + (1 << i); if(t <= n && get(t) < x) { curr = t; } } return curr + 1; } }; // ------------------- LCA_O1 (LCA using Euler Tour & Sparse Table) for 1-indexed nodes ----------------------- template<typename T = int> struct LCA_O1 { vector<int> enter; vpii euler; vector<vector<pii>> st; vector<int> log_table; int timer; LCA_O1() {} // here graph is 1-indexed; we assume nodes from 1 to n. LCA_O1(const vt<vt<T>> &graph, int root = 1) : timer(1) { int n = graph.size() - 1; // graph[1..n] enter.resize(n + 1, -1); dfs(root, -1, 0, graph); int m = euler.size(); log_table.resize(m + 1); for (int i = 2; i <= m; i++) log_table[i] = log_table[i / 2] + 1; int K = log_table[m] + 1; st.assign(K, vector<pii>(m)); for (int i = 0; i < m; i++) st[0][i] = euler[i]; for (int j = 1; j < K; j++) { for (int i = 0; i + (1 << j) <= m; i++) { pii a = st[j - 1][i], b = st[j - 1][i + (1 << (j - 1))]; st[j][i] = (a.first < b.first ? a : b); } } } void dfs(int node, int par, int d, const vt<vt<T>> &graph) { enter[node] = timer; euler.push_back({d, node}); for(auto nxt : graph[node]) { if(nxt == par) continue; dfs(nxt, node, d + 1, graph); euler.push_back({d, node}); timer++; } timer++; } int lca(int u, int v) { int L = min(enter[u], enter[v]); int R = max(enter[u], enter[v]); int j = log_table[R - L + 1]; pii a = st[j][L - 1], b = st[j][R - (1 << j) + 1 - 1]; return (a.first < b.first ? a : b).second; } }; // ------------------- GRAPH Class for 1-indexed nodes ----------------------- template<typename T = int> class GRAPH { public: int n, m; vvi dp; vi depth, parent, subtree; vi tin, tout, ord; int timer = 1; LCA_O1<T> lca_01; GRAPH() {} // graph is given as 1-indexed: indices 1..n, graph[0] is unused. GRAPH(const vt<vt<T>>& graph, int root = 1) : lca_01(graph, root) { n = graph.size() - 1; m = log2(n) + 1; dp.resize(n + 1, vi(m, root)); // dp[1..n] depth.resize(n + 1, 0); parent.resize(n + 1, -1); subtree.resize(n + 1, 1); tin.resize(n + 1); tout.resize(n + 1); ord.resize(n + 1); dfs(graph, root, -1); init(); } // DFS: node from 1..n; par = -1 for root. void dfs(const vt<vt<T>>& graph, int node, int par) { tin[node] = timer++; ord[tin[node]] = node; for(auto nxt : graph[node]) { if(nxt == par) continue; depth[nxt] = depth[node] + 1; dp[nxt][0] = node; parent[nxt] = node; dfs(graph, nxt, node); subtree[node] += subtree[nxt]; } tout[node] = timer - 1; } bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tin[v] <= tout[u]; } void init() { for(int j = 1; j < m; j++) { for(int i = 1; i <= n; i++) { dp[i][j] = dp[dp[i][j - 1]][j - 1]; } } } int lca(int a, int b) { return lca_01.lca(a, b); } int dist(int u, int v) { int a = lca(u, v); return depth[u] + depth[v] - 2 * depth[a]; } int k_ancestor(int a, int k) { for(int i = m - 1; i >= 0; i--) { if((k >> i) & 1) a = dp[a][i]; } return a; } }; // ------------------- FW for 1-indexed BIT already defined above ----------------------- // ------------------- Main solve() for 1-indexed system ----------------------- const int MK = 20; void solve() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; // We'll work with nodes 1..n // Allocate graph with size n+1 (ignore index 0) vt<vt<int>> graph(n + 1); vpii edges(n); // edges[1..n-1] for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; // assume input is 1-indexed; no conversion needed. edges[i] = {u, v}; graph[u].push_back(v); graph[v].push_back(u); } // Build GRAPH with root = 1. GRAPH<int> g(graph, 1); // Reorient edges so that for each edge, the first is the parent and the second is the child. for (int i = 1; i <= n - 1; i++) { auto &e = edges[i]; int u = e.first, v = e.second; if(g.parent[v] != u) swap(u, v); e = {u, v}; } // Build BIT (FW) with size n, for Euler tour indices in [1, n]. FW<int> BITree(n, 0, [](const int &a, const int &b) { return a + b; }); // Initialize BIT: for every node i (1-indexed), update at position tin[i] with +1. for (int i = 1; i <= n; i++) { BITree.update_at(g.tin[i], 1); } // Use the full dp table size for binary lifting. int liftSize = g.dp[1].size(); // dp[1]..dp[n] auto find_par = [&](int u) -> int { int x = BITree.get(g.tin[u]); for (int j = liftSize - 1; j >= 0; j--) { int p = g.dp[u][j]; if(p < 1 || p > n) continue; // Here we use >= in case updates cause BIT value to become larger if(BITree.get(g.tin[p]) >= x) u = p; } return u; }; // used[] for edge toggling; initialize ans[] to 1 for every node; del[] as auxiliary. vi used(n, 0), ans(n + 1, 1), del(n + 1, 0); // Process m operations (edge toggles). // Edge ids are given 1-indexed. for (int i = 1; i <= m; i++) { int k; cin >> k; // k is between 1 and n-1. auto &e = edges[k]; int u = e.first, v = e.second; if(!used[k]) { // Remove edge: cut subtree v from u. ans[find_par(u)] += ans[v] - del[v]; BITree.update_range(g.tin[v], g.tout[v], -1); } else { // Add edge: merge subtree v back with u. ans[v] = del[v] = ans[find_par(u)]; BITree.update_range(g.tin[v], g.tout[v], 1); } used[k] ^= 1; } // Process q queries: for each query node u (1-indexed), output the aggregate of its component. while(q--) { int u; cin >> u; assert(u >= 1 && u <= n); cout << ans[find_par(u)] << "\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); 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...