Submission #1261767

#TimeUsernameProblemLanguageResultExecution timeMemory
1261767Szymon_PilipczukTourism (JOI23_tourism)C++20
7 / 100
940 ms35052 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define st first #define nd second #define pb push_back #define all(a) a.begin(),a.end() #define rep(a,b) for(int a = 0;a<b;a++) const int inf = 1e9; const ll infl = 1e18; vector<int> gr[100000]; int pr[100000]; int rpr[100000]; int cpr = 0; int ps[100000]; int cps = 0; bool vis[100000]; int jp[100000][20]; int d[100000]; int c[100000]; void dfs(int v,int cd) { vis[v] = true; pr[v] = cpr; rpr[cpr] = v; cpr++; d[v] = cd; for(int i : gr[v]) { if(!vis[i]) { jp[i][0] = v; dfs(i,cd+1); } } ps[v] = cps; cps++; } int lca(int a,int b) { if(d[a] < d[b]) swap(a,b); for(int i = 19;i>=0;i--) { if(d[a] - (1<<i) >= d[b]) { a = jp[a][i]; } } for(int i = 19;i>=0;i--) { if(jp[a][i] != jp[b][i]) { a = jp[a][i]; b = jp[b][i]; } } if(a==b)return a; return jp[a][0]; } bool intr(int a,int b) { return (pr[a] <= pr[b] && ps[a] >= ps[b]); } vector<pair<pair<int,int>,int>> cu; vector<pair<pair<int,int>,int>> nx; vector<pair<int,int>> cp; vector<pair<int,int>> nxp; int last; int trize; vector<int> tr; int tans[100000]; void add(int p,int v) { if(p >= inf) return; p+=trize; tr[p] += v; p/=2; while(p > 0) { tr[p] = tr[p*2] + tr[p*2+1]; p/=2; } } int check(int l,int r) { l+=trize; r+=trize; int ans = tr[l]; if(l!=r)ans+=tr[r]; while(l/2 != r/2) { if(l%2==0)ans+=tr[l+1]; if(r%2==1)ans+=tr[r-1]; l/=2;r/=2; } return ans; } void solve(int l,int r) { if(l > r) return; unordered_map<int,int> conv; int ize = r-l+1; vector<int> vtr; int root = (l+r)/2; vector<pair<pair<int,int>,int>> cc; while(last < cu.size() && cu[last].st.st <= root) { if(cu[last].st.nd >= root) { cc.pb(cu[last]); } else { nx.pb(cu[last]); } last++; } unordered_set<int> used; for(int i = l;i<=r;i++) { vtr.pb(pr[c[i]]); used.insert(c[i]); } for(int i = l;i<r;i++) { int cv = lca(c[i],c[i+1]); //cerr<<cv<<"\n"; if(!used.contains(cv)) { vtr.pb(pr[cv]); used.insert(cv); } } //cerr<<"\n"; sort(all(vtr)); rep(i,vtr.size()) { vtr[i] = rpr[vtr[i]]; //cerr<<vtr[i]<<"\n"; conv[vtr[i]] = i; } vector<pair<int,int>> o(vtr.size()); o[0] = {-1,-1}; for(int i = 1;i<vtr.size();i++) { int cv = i-1; while(!intr(vtr[cv],vtr[i])) { cv = o[cv].st; } o[i] = {cv,d[vtr[i]]-d[vtr[cv]]}; //cerr<<o[i].st<<" "<<o[i].nd<<"\n"; } int troot = conv[c[root]]; int cw = troot; int prev = -1; int nxv = o[cw].st; int pv = -1; int nv = o[cw].nd; while(true) { o[cw] = {prev,pv}; prev = cw; pv = nv; cw = nxv; if(cw == -1) break; nxv = o[cw].st; nv = o[cw].nd; } vector<pair<int,int>> kr(vtr.size(),{inf,inf}); kr[troot] = {0,0}; for(int i = root-1;i>=l;i--) { int cv = conv[c[i]]; while(kr[cv].st == inf) { kr[cv].st = root-i; cv = o[cv].st; } } /*cerr<<"\n"; for(int i = 0;i<vtr.size();i++) { cerr<<kr[i].st<<" "<<kr[i].nd<<"\n"; } cerr<<"\n";*/ vector<pair<pair<int,int>,int>> am; for(int i = root+1;i<=r;i++) { int cv = conv[c[i]]; while(kr[cv].nd == inf) { kr[cv].nd = i-root; //am.pb({kr[cv],o[cv].nd}); cv = o[cv].st; } } rep(i,vtr.size()) { if(kr[i].st != 0) { am.pb({kr[i],o[i].nd}); } } /*cerr<<"\n"; for(int i = 0;i<vtr.size();i++) { cerr<<kr[i].st<<" "<<kr[i].nd<<" "<<o[i].nd<<"\n"; } cerr<<"\n";*/ sort(all(am)); sort(all(cc)); reverse(all(cc)); tr.clear(); trize = (r-root+1); tr.resize(2*trize); rep(i,am.size()) { add(am[i].st.nd,am[i].nd); //cerr<<am[i].st.st<<" "<<am[i].st.nd<<" "<<am[i].nd<<"\n"; } int ans = 0; int j = 0; rep(i,cc.size()) { while(j < am.size() && root-cc[i].st.st >= am[j].st.st) { ans += am[j].nd; add(am[j].st.nd,-am[j].nd); j++; } //cerr<<ans<<" "<<check(0,cc[i].st.nd-root)<<" "<<root<<" "<<cc[i].nd<<"\n"; tans[cc[i].nd] = ans + check(0,cc[i].st.nd-root) + 1; } nxp.pb({l,root-1}); nxp.pb({root+1,r}); } int main() { int n,m,q; cin>>n>>m>>q; rep(i,n-1) { int a,b; cin>>a>>b; a--;b--; gr[a].pb(b); gr[b].pb(a); } dfs(0,0); jp[0][0] = 0; for(int i = 1;i<20;i++) { rep(j,n) { jp[j][i] = jp[jp[j][i-1]][i-1]; } } rep(i,m) { cin>>c[i]; c[i]--; } rep(i,q) { int a,b; cin>>a>>b; a--;b--; nx.pb({{a,b},i}); } nxp.pb({0,m-1}); sort(all(nx)); while(!nx.empty()) { cu = nx; last = 0; cp = nxp; nxp.clear(); nx.clear(); for(pair<int,int> i : cp) { solve(i.st,i.nd); } while(last < cu.size()) { nx.pb(cu[last]); last++; } } rep(i,q) { cout<<tans[i]<<"\n"; } }
#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...