Submission #1091743

#TimeUsernameProblemLanguageResultExecution timeMemory
1091743DucNguyen2007Tourism (JOI23_tourism)C++14
0 / 100
5091 ms13744 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=1e5+5,LG=__lg(maxN)+1,BLOCK=321; const ll inf=2e18; int n,m,q,h[maxN+1],up[maxN+1][LG+1],num[maxN+1],timer=0,sl=0,a[maxN+1],tour[maxN+1]; vector<int> adj[maxN+1]; void dfs(ll u) { tour[++timer]=u; num[u]=timer; for(auto v:adj[u]) { if(v==up[u][0]) { continue; } h[v]=h[u]+1; up[v][0]=u; for(int j=1;j<=LG;j++) { up[v][j]=up[up[v][j-1]][j-1]; } dfs(v); } } int lca(int u,int v) { if(h[u]<h[v]) { swap(u,v); } for(int j=LG;j>=0;j--) { if(h[up[u][j]]>=h[v]) { u=up[u][j]; } } for(int j=LG;j>=0;j--) { if(up[u][j]!=up[v][j]) { u=up[u][j]; v=up[v][j]; } } if(u==v) { return u; } else return up[u][0]; } int dist(int u,int v) { int p=lca(u,v); return h[u]+h[v]-2*h[p]; } struct fenwick { int bit[maxN+1]; fenwick() { memset(bit,0,sizeof(bit)); } void update(int u,int val) { for(int i=u;i<=n;i+=(i&(-i))) { bit[i]+=val; } } int get(int u) { int ans=0; for(int i=u;i>0;i-=(i&(-i))) { ans+=bit[i]; } return ans; } int get_first() { int i=0; for(int j=LG;j>=0;j--) { if(i+(1LL<<j)<n&&get(i+(1LL<<j))==0) { i+=(1LL<<j); } } return i+1; } int get_last() { int i=n+1; for(int j=LG;j>=0;j--) { if(i-(1LL<<j)>1&&get(n)-get(i-(1LL<<j)-1)==0) { i-=(1LL<<j); } } return i-1; } int lower(int u) { int pos=num[u],i=0; int tmp=get(pos); for(int j=LG;j>=0;j--) { if(i+(1LL<<j)<pos&&tmp-get(i+(1LL<<j)-1)>0) { i+=(1LL<<j); } } if(i==0) { return get_last(); } return i; } int upper(int u) { int pos=num[u],i=n+1; int tmp=get(pos); for(int j=LG;j>=0;j--) { if(i-(1LL<<j)>pos&&get(i+(1LL<<j))-tmp>0) { i-=(1LL<<j); } } if(i==n+1) { return get_first(); } return i; } }f; void add(int u) { if(f.get(n)==0) { f.update(num[u],1); return; } int l=tour[f.lower(u)],r=tour[f.upper(u)]; sl-=dist(l,r); sl+=(dist(l,u)+dist(u,r)); //cout<<l<<" "<<r<<" "<<sl<<'\n'; f.update(num[u],1); } void del(int u) { if(f.get(n)==1) { f.update(num[u],-1); return; } int l=f.lower(u),r=f.upper(u); sl+=dist(l,r); sl-=(dist(l,u)+dist(u,r)); f.update(num[u],-1); } struct query { int l,r,id; }p[maxN+1]; int ans[maxN+1],cnt[maxN+1]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<n;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } h[1]=1; dfs(1); for(int i=1;i<=m;i++) { cin>>a[i]; } for(int i=1;i<=q;i++) { cin>>p[i].l>>p[i].r; p[i].id=i; } sort(p+1,p+q+1,[&](query x,query y) { if(x.r/BLOCK==y.r/BLOCK) { return x.l<y.l; } return x.r/BLOCK<y.r/BLOCK; }); int lc=1,rc=0; for(int i=1;i<=q;i++) { int l=p[i].l,r=p[i].r,id=p[i].id; while(rc<r) { rc++; if(!cnt[a[rc]]) { add(a[rc]); } cnt[a[rc]]++; } while(lc>l) { lc--; if(!cnt[a[lc]]) { add(a[lc]); } cnt[a[lc]]++; } while(rc>r) { cnt[a[rc]]--; if(!cnt[a[rc]]) { del(a[rc]); } rc--; } while(lc<l) { cnt[a[lc]]--; if(!cnt[a[lc]]) { del(a[lc]); } lc++; } ans[id]=sl/2; } for(int i=1;i<=q;i++) { cout<<ans[i]+1<<'\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...