Submission #1192761

#TimeUsernameProblemLanguageResultExecution timeMemory
1192761adhityamvTourism (JOI23_tourism)C++20
28 / 100
5095 ms78396 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> #include <stack> using namespace std; #define int long long #define mp make_pair #define fi first #define pii pair<int,int> #define se second const int INF=1000000000000000000; //const int INF=1e9; const int N=1000000; //const int M=998244353; const int ln=20; template<typename T> std::ostream& operator<< (std::ostream& os,pair<T,T> p){ return os << p.fi << "," << p.se << " "; } vector<int> edges[N]; int parent[N]; int depth[N]; int lpos[N]; int rpos[N]; vector<int> et; vector<int> det; void dfs(int u,int p){ parent[u]=p; lpos[u]=rpos[u]=et.size(); et.push_back(u); det.push_back(depth[u]); for(int v:edges[u]){ if(v==p) continue; depth[v]=depth[u]+1; dfs(v,u); rpos[u]=et.size(); et.push_back(u); det.push_back(depth[u]); } } int sq=300; int pow2[N]; void solve(){ int n,m,q; cin >> n >> m >> q; for(int i=0;i<n-1;i++){ int u,v; cin >> u >> v; u--,v--; edges[u].push_back(v); edges[v].push_back(u); } depth[0]=0; dfs(0,-1); int c[m]; for(int i=0;i<m;i++){ cin >> c[i]; c[i]--; } pair<pii,int> queries[q]; for(int i=0;i<q;i++){ int l,r; cin >> l >> r; l--; queries[i]=mp(mp(l,r),i); } sort(queries,queries+q,[&](pair<pii,int> p1,pair<pii,int> p2){ return mp(p1.fi.fi/sq,(2*((p1.fi.fi/sq)%2)-1)*p1.fi.se)<mp(p2.fi.fi/sq,(2*((p2.fi.fi/sq)%2)-1)*p2.fi.se); }); int sptb[2*n-1][ln]; for(int i=0;i<2*n-1;i++) sptb[i][0]=det[i]; for(int j=0;j<ln-1;j++){ for(int i=0;i<2*n-1;i++){ if(i+(1<<j)>=2*n-1){ sptb[i][j+1]=sptb[i][j]; } else sptb[i][j+1]=min(sptb[i][j],sptb[i+(1<<j)][j]); } } auto lca=[&](int u,int v){ int l=min(lpos[u],lpos[v]); int r=max(lpos[u],lpos[v])+1; int sz=pow2[r-l]; int o1=sptb[l][sz]; int o2=sptb[r-(1<<sz)][sz]; return min(o1,o2); }; int cl=0; int cr=0; int cans=0; int ans[q]; //for(int i:et) cout << i << " "; //cout << "\n"; multiset<int> lposes; for(int i=0;i<q;i++){ int l=queries[i].fi.fi; int r=queries[i].fi.se; int ind=queries[i].se; auto inc=[&](int ci)->void{ //cout << ci << ">?\n"; auto it=lposes.insert(lpos[c[ci]]); auto nit=next(it,1); cans+=depth[c[ci]]; if(it==lposes.begin() && nit==lposes.end()){ return; } if(it==lposes.begin() && nit!=lposes.end()){ cans-=lca(c[ci],et[*nit]); return; } auto pit=next(it,-1); if(nit==lposes.end()){ cans-=lca(c[ci],et[*pit]); return; } cans+=lca(et[*pit],et[*nit]); cans-=lca(c[ci],et[*pit]); cans-=lca(c[ci],et[*nit]); }; auto rem=[&](int ci)->void{ auto it=lposes.find(lpos[c[ci]]); auto nit=next(it,1); cans-=depth[c[ci]]; if(it==lposes.begin() && nit==lposes.end()){ lposes.erase(it); return; } if(it==lposes.begin() && nit!=lposes.end()){ cans+=lca(c[ci],et[*nit]); lposes.erase(it); return; } auto pit=next(it,-1); if(nit==lposes.end()){ cans+=lca(c[ci],et[*pit]); lposes.erase(it); return; } cans-=lca(et[*pit],et[*nit]); cans+=lca(c[ci],et[*pit]); cans+=lca(c[ci],et[*nit]); lposes.erase(it); }; while(cr<r){ inc(cr); cr++; } while(cl>l){ cl--; inc(cl); } while(cl<l){ rem(cl); cl++; } while(cr>r){ cr--; rem(cr); } ans[ind]=cans-lca(et[*lposes.begin()],et[*lposes.rbegin()]); } for(int i=0;i<q;i++) cout << ans[i]+1 << "\n"; } signed main(){ auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); pow2[1]=0; for(int i=2;i<N;i++){ if(i==(1<<(pow2[i-1]+1))) pow2[i]=pow2[i-1]+1; else pow2[i]=pow2[i-1]; } int t; //cin >> t; t=1; while(t--) solve(); auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...