Submission #1217488

#TimeUsernameProblemLanguageResultExecution timeMemory
1217488noyancanturkTwo Currencies (JOI23_currencies)C++20
100 / 100
896 ms44204 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back using pii=pair<int,int>; const int lim=2e5+100; struct{ int tree[lim]; void update(int p,int val){ while(p<lim){ tree[p]+=val; p+=p&-p; } } void init(){ for(int i=0;i<lim;i++){ tree[i]=0; } } int query(int p){ int ans=0; while(p){ ans+=tree[p]; p-=p&-p; } return ans; } int query(int l,int r){ if(r<l)return 0; return query(r)-query(l-1); } }fw1,fw2; vector<int>v[lim]; int tin[lim],tt=1; int sz[lim],par[lim],head[lim]; int sbs(int node){ for(int i=0;i<v[node].size();i++){ if(v[node][i]==par[node]){ swap(v[node][i],v[node].back()); v[node].pop_back(); break; } } sz[node]=1; for(int j:v[node]){ par[j]=node; sz[node]+=sbs(j); } return sz[node]; } void build(int node){ tin[node]=tt++; if(!head[node])head[node]=node; if(!v[node].size())return; int heavy=v[node][0]; for(int j:v[node]){ if(sz[heavy]<sz[j]){ heavy=j; } } head[heavy]=head[node]; build(heavy); for(int j:v[node]){ if(j==heavy)continue; build(j); } } pii query(int x,int y){ int ans1=0,ans2=0; while(1){ if(tin[y]<tin[x])swap(x,y); if(head[x]==head[y]){ ans1+=fw1.query(tin[x]+1,tin[y]); ans2+=fw2.query(tin[x]+1,tin[y]); break; } ans1+=fw1.query(tin[head[y]],tin[y]); ans2+=fw2.query(tin[head[y]],tin[y]); y=par[head[y]]; } return {ans1,ans2}; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,m,q; cin>>n>>m>>q; pii edges[n-1]; for(int i=0;i<n-1;i++){ int x,y; cin>>x>>y; edges[i]={x,y}; v[x].pb(y); v[y].pb(x); } pii guys[m]; for(int i=0;i<m;i++){ cin>>guys[i].second>>guys[i].first; guys[i].second--; } sort(guys,guys+m); sbs(1); build(1); for(int i=0;i<n-1;i++){ if(edges[i].first!=par[edges[i].second])swap(edges[i].first,edges[i].second); } for(int i=0;i<m;i++){ guys[i].second=edges[guys[i].second].second; } int a[q],b[q],c[q],d[q]; for(int i=0;i<q;i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; } vector<int>mids[m+1]; int l[q],r[q],ans[q]; for(int i=0;i<q;i++){ l[i]=0,r[i]=m; ans[i]=-1; mids[m>>1].pb(i); } for(int i=0;i<17;i++){ fw1.init(); fw2.init(); for(int mid=0;mid<m;mid++){ fw1.update(tin[guys[mid].second],1); } for(int mid=0;mid<=m;mid++){ for(int j:mids[mid]){ auto[ans1,ans2]=query(a[j],b[j]); if(ans1<=c[j]&&ans2<=d[j]){ ans[j]=c[j]-ans1; l[j]=mid+1; if(l[j]<=r[j])mids[(l[j]+r[j])>>1].pb(j); }else if(ans1<=c[j]){ r[j]=mid-1; if(l[j]<=r[j])mids[(l[j]+r[j])>>1].pb(j); }else if(ans2<=d[j]){ l[j]=mid+1; if(l[j]<=r[j])mids[(l[j]+r[j])>>1].pb(j); } } mids[mid].clear(); if(mid!=m){ fw1.update(tin[guys[mid].second],-1); fw2.update(tin[guys[mid].second],guys[mid].first); } } } for(int j:ans)cout<<j<<'\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...