Submission #999242

#TimeUsernameProblemLanguageResultExecution timeMemory
999242DzadzoTourism (JOI23_tourism)C++17
100 / 100
701 ms54212 KiB
#include <bits/stdc++.h> #define ll long long #define int ll #define pb push_back #define S second #define F first #define pii pair<int,int> #define vi vector <int> #define vvi vector <vi> #define vvvi vector <vvi> #define vp vector <pii> #define vvp vector <vp> #define vb vector <bool> #define vvb vector <vb>; #define INF LLONG_MAX #define MOD 1000000007 #define MAXN 100005 using namespace std; set <pair<int,pii>> myset; int bit[MAXN+1]; vvi P(MAXN+1,vi(20)); void add(int idx,int delta){ for (;idx<=MAXN;idx+=idx&-idx)bit[idx]+=delta; } int get(int idx){ int res=0; for (;idx>0;idx-=idx&-idx)res+=bit[idx]; return res; } int n; void update(int l,int r,int val){ if(l>r)return; if (r>n)return; if (l<=0)return; auto it=myset.lower_bound({l,{0,0}}); add(val,r-l+1); if ((*it).F!=l){ it--; if ((*it).S.F<r){ add((*it).S.S,-((*it).S.F-l+1)); myset.insert({(*it).F,{l-1,(*it).S.S}}); myset.erase(*it); }else if ((*it).S.F>=r){ add((*it).S.S,-(r-l+1)); myset.insert({(*it).F,{l-1,(*it).S.S}}); if ((*it).S.F!=r) myset.insert({r+1,{(*it).S.F,(*it).S.S}}); myset.erase(*it); myset.insert({l,{r,val}}); return; } } it=myset.lower_bound({l,{0,0}}); vector <pair <int,pii>> del; for (;;it++){ if (it==myset.end())break; if ((*it).F>r)break; del.pb(*it); if ((*it).S.F>r){ add((*it).S.S,-(r-((*it).F)+1)); myset.insert({r+1,{(*it).S.F,(*it).S.S}}); break; }else add((*it).S.S,-((*it).S.F-(*it).F+1)); } myset.insert({l,{r,val}}); for (auto x:del)myset.erase(x); } vvi adj(MAXN+1); vi s(MAXN+1),tin(MAXN+1),tout(MAXN+1),dep(MAXN+1),par(MAXN+1); int timer=0; void dfs(int v,int p){ tin[v]=++timer; par[v]=p; s[v]=1; P[v][0]=p; for (int i=1;i<20;i++)P[v][i]=P[P[v][i-1]][i-1]; dep[v]=dep[par[v]]+1; for (int to:adj[v])if(to!=p)dfs(to,v),s[v]+=s[to]; tout[v]=++timer; } vp T(4*MAXN+1); vi c(MAXN+1); void build(int v,int tl,int tr){ if (tl==tr)T[v]={tin[c[tl]],tout[c[tl]]};else{ int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); T[v]={min(T[2*v].F,T[2*v+1].F),max(T[2*v].S,T[2*v+1].S)}; } } pii gettime(int v,int tl,int tr,int l,int r){ if (l>r)return {INF,0}; if (tl==l && tr==r)return T[v]; int tm=(tl+tr)/2; pii L=gettime(v*2,tl,tm,l,min(r,tm)); pii R=gettime(v*2+1,tm+1,tr,max(l,tm+1),r); return {min(L.F,R.F),max(L.S,R.S)}; } vi head(MAXN+1),ind(MAXN+1);int cnt; void decomp(int v,int h){ head[v]=h; ind[v]=++cnt; pii best={0,0}; for (int to:adj[v])if (to!=par[v])best=max(best,{s[to],to}); if(!best.S)return; decomp(best.S,h); for (int to:adj[v])if(to!=best.S && to!=par[v])decomp(to,to); } void up(int a,int b,int val){ for (;head[a]!=head[b];b=par[head[b]]){ if (dep[head[a]]>dep[head[b]])swap(a,b); update(ind[head[b]],ind[b],val); } if (dep[a]>dep[b])swap(a,b); update(ind[a],ind[b],val); } int calc(int v,int t1,int t2){ if (t1>=tin[v] && t2<=tout[v])return dep[v]-1; int res=v; for (int bit=19;bit>=0;bit--){ if (!P[res][bit])continue; if (t1<tin[P[res][bit]] || t2>tout[P[res][bit]])res=P[res][bit]; } return dep[res]-2; } signed main(){ ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int m,q; cin>>n>>m>>q; for (int i=1;i<n;i++){ int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } for (int i=1;i<=m;i++)cin>>c[i]; dfs(1,0); build(1,1,m); decomp(1,1); myset.insert({1,{n,100001}});add(100001,n); vvp Q(MAXN+1); for (int i=1;i<=q;i++){ int l,r; cin>>l>>r; Q[l].pb({r,i}); } int ans[q+1]; for (int l=m;l>=1;l--){ up(c[l],1,l); for (auto &[r,id]:Q[l]){ pii x=gettime(1,1,m,l,r); ans[id]=get(r)-get(l-1)-calc(c[l],x.F,x.S); } } for (int i=1;i<=q;i++)cout<<ans[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...