Submission #1280947

#TimeUsernameProblemLanguageResultExecution timeMemory
1280947IcelastTourism (JOI23_tourism)C++20
28 / 100
5091 ms26316 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; struct Tree{ int n, root; vector<int> depth, head, sz, pa; vector<int> f; Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){ depth.resize(n+1, -1); head.resize(n+1); sz.resize(n+1, 0); pa.resize(n+1, -1); auto rootTree = [&](auto rootTree, int u, int p) -> void{ depth[u] = depth[p]+1; pa[u] = p; sz[u] = 1; for(int v : adj[u]){ if(v == p) continue; rootTree(rootTree, v, u); sz[u] += sz[v]; } }; rootTree(rootTree, root, 0); auto decompose = [&](auto decompose, int u, int h) -> void{ head[u] = h; int heavy = -1; for(int v : adj[u]){ if(v == pa[u]) continue; if(heavy == -1 || sz[heavy] < sz[v]) heavy = v; } if(heavy != -1) decompose(decompose, heavy, h); for(int v : adj[u]){ if(v == pa[u] || v == heavy) continue; decompose(decompose, v, v); } }; decompose(decompose, root, root); f = [&]{ vector<array<int, 2>> first(n+1); vector<array<int, 2>> second(n+1); function<void(int, int)> dfs0 = [&](int u, int p) { first[u] = second[u] = {0, -1}; for (int v : adj[u]) { if (v == p) { continue; } dfs0(v, u); auto fetch = first[v]; fetch[0] += 1; fetch[1] = v; if (fetch > first[u]) { swap(fetch, first[u]); } if (fetch > second[u]) { swap(fetch, second[u]); } } }; dfs0(1, 0); function<void(int, int)> dfs = [&](int u, int p) { for (int v : adj[u]) { if (v == p) { continue; } auto fetch = first[u][1] == v ? second[u] : first[u]; fetch[0] += 1; fetch[1] = u; if (fetch > first[v]) { swap(fetch, first[v]); } if (fetch > second[v]) { swap(fetch, second[v]); } dfs(v, u); } }; dfs(1, 0); vector<int> f(n+1); for (int u = 1; u <= n; u++) { f[u] = first[u][0]; } return f; }(); }; int lca(int u, int v){ for(; head[u] != head[v]; v = pa[head[v]]){ if(depth[head[u]] > depth[head[v]]) swap(u, v); } if(depth[u] > depth[v]) swap(u, v); return u; } int dist(int u, int v) { return depth[u]+depth[v]-2*depth[lca(u, v)]; } }; struct que{ int l, r, id; }; void solve(){ int n, m, Q; cin >> n >> m >> Q; vector<vector<int>> adj(n+1); for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } vector<int> b(m+1); for(int i = 1; i <= m; i++){ cin >> b[i]; } vector<que> q; for(int i = 1; i <= Q; i++){ int l, r; cin >> l >> r; q.push_back({l, r, i}); } Tree Y(n, 1, adj); vector<int> tin(n+1), node(n+1); int timer = 0; auto dfs = [&](auto dfs, int u, int p) -> void{ timer++; tin[u] = timer; node[timer] = u; for(int v : adj[u]){ if(v == p) continue; dfs(dfs, v, u); } }; dfs(dfs, 1, 0); int B = 1000; sort(q.begin(), q.end(), [&](que a, que b){ if(a.l/B != b.l/B){ return a.l < b.l; } return a.r < b.r; }); set<int> s; int ans = 0; vector<int> cnt(n+1, 0); auto add = [&](int u) -> void{ cnt[u]++; if(cnt[u] > 1){ return; } int x = tin[u]; if(s.size() >= 1){ auto it = s.lower_bound(x); if(it == s.begin()){ it = prev(s.end()); }else{ it--; } int v1 = node[*it]; it++; if(it == s.end()) it = s.begin(); int v2 = node[*it]; ans -= Y.dist(v1, v2); ans += Y.dist(v1, u); ans += Y.dist(u, v2); } s.insert(x); }; auto del = [&](int u) -> void{ cnt[u]--; if(cnt[u] > 0){ return; } int x = tin[u]; if(s.size() >= 1){ auto it = s.lower_bound(x); if(it == s.begin()){ it = prev(s.end()); }else{ it--; } int v1 = node[*it]; it++; if(it == s.end()) it = s.begin(); it++; if(it == s.end()) it = s.begin(); int v2 = node[*it]; ans += Y.dist(v1, v2); ans -= Y.dist(v1, u); ans -= Y.dist(u, v2); } s.erase(x); }; vector<int> res(Q+1); int l = 1, r = 0; for(auto it : q){ int L = it.l, R = it.r, id = it.id; while(r < R){ r++; add(b[r]); } while(r > R){ del(b[r]); r--; } while(l < L){ del(b[l]); l++; } while(l > L){ l--; add(b[l]); } res[id] = ans/2 + 1; } for(int i = 1; i <= Q; i++){ cout << res[i] << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...