제출 #862179

#제출 시각아이디문제언어결과실행 시간메모리
862179imarnTwo Currencies (JOI23_currencies)C++14
100 / 100
3057 ms211180 KiB
#include "bits/stdc++.h" #define f first #define s second #define ll long long #define pb push_back #define pii pair<ll,ll> using namespace std; const int N=1e5+5; vector<pair<int,vector<ll>>>g[N]; int sz[N],head[N],pr[N],dep[N],idl[N],idr[N]; pair<ll,pii> a[4*N]; vector<pair<int,pii>>t[16*N]; int n; void build(int i,int l,int r){ if(l==r)return void(t[i].pb({a[l].s.s,{a[l].f,a[l].f}})); int m=(l+r)>>1; build(2*i,l,m);build(2*i+1,m+1,r); int li=0,ri=0; while(li<t[2*i].size()&&ri<t[2*i+1].size()){ if(t[2*i][li].f<t[2*i+1][ri].f)t[i].pb({t[2*i][li].f,{t[2*i][li].s.f,t[2*i][li].s.f}}),li++; else t[i].pb({t[2*i+1][ri].f,{t[2*i+1][ri].s.f,t[2*i+1][ri].s.f}}),ri++; }while(li<t[2*i].size())t[i].pb({t[2*i][li].f,{t[2*i][li].s.f,t[2*i][li].s.f}}),li++; while(ri<t[2*i+1].size())t[i].pb({t[2*i+1][ri].f,{t[2*i+1][ri].s.f,t[2*i+1][ri].s.f}}),ri++; for(int j=1;j<t[i].size();j++)t[i][j].s.s=t[i][j-1].s.s+t[i][j].s.f; } pii qr(int i,int l,int r,int tl,int tr,int x){ if(r<tl||l>tr)return {0,0}; if(r<=tr&&l>=tl){ int le=0,re=t[i].size()-1; if(x<t[i][0].f)return {0,0}; while(le<re){ int md=(le+re+1)>>1; if(t[i][md].f<=x)le=md; else re=md-1; }return {t[i][le].s.s,le+1}; } int m=(l+r)>>1; pii qll=qr(2*i,l,m,tl,tr,x),qrr=qr(2*i+1,m+1,r,tl,tr,x); return {qll.f+qrr.f,qll.s+qrr.s}; } int dfs(int u,int p){ sz[u]=1; pr[u]=p; for(auto v:g[u]){ if(v.f==p)continue; dep[v.f]=dep[u]+1; sz[u]+=dfs(v.f,u); }return sz[u]; }int cnt=1; void hld(int u,vector<ll> w,int p,int h){ idl[u]=cnt; for(auto it : w){ a[cnt].f = it; a[cnt].s.f = cnt++; }idr[u]=cnt-1; head[u]=h; int x=-1,y=-1;vector<ll>z; for(auto v:g[u]){ if(v.f==p)continue; if(sz[v.f]>y)y=sz[v.f],x=v.f,z=v.s; }if(x==-1)return; hld(x,z,u,h); for(auto v:g[u]){ if(v.f==p||v.f==x)continue; hld(v.f,v.s,u,v.f); } } pii path(int x,int y,ll v,pii res={0,0}){ while(head[x]!=head[y]){ if(dep[head[x]]<dep[head[y]])swap(x,y); pii tmp=qr(1,1,cnt-1,idl[head[x]],idr[x],v); res.f+=tmp.f;res.s+=tmp.s; x=pr[head[x]]; }if(dep[x]>dep[y])swap(x,y); pii tmp=qr(1,1,cnt-1,idr[x]+1,idr[y],v); res.f+=tmp.f;res.s+=tmp.s; return res; }pii road[N];vector<ll> W[N]; bool cmp(pair<ll,pii> x,pair<ll,pii> y){ return x.s.f<y.s.f; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int m,q;cin>>n>>m>>q; for(int i=1;i<=n-1;i++)cin>>road[i].f>>road[i].s; for(int i=1;i<=n;i++)W[i].pb(0); for(int i=1;i<=m;i++){ int u;ll w;cin>>u>>w; W[u].pb(w); }for(int i=1;i<=n-1;i++)g[road[i].f].pb({road[i].s,W[i]}),g[road[i].s].pb({road[i].f,W[i]}); dfs(1,1);hld(1,{0},1,1); sort(a+1,a+cnt); for(int i=1;i<cnt;i++)a[i].s.s=i; sort(a+1,a+cnt,cmp); build(1,1,cnt-1); while(q--){ int st,ed;ll x,y;cin>>st>>ed>>x>>y; ll dist = path(st,ed,cnt).s; ll l=1,r=cnt-1; while(l<r){ ll md=(l+r+1)>>1; pii tmp = path(st,ed,md); if(tmp.f>y)r=md-1; else l=md; }pii tmp = path(st,ed,l); if(tmp.s+x>=dist)cout<<x-dist+tmp.s<<"\n"; else cout<<-1<<"\n"; } }

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp: In function 'void build(int, int, int)':
currencies.cpp:19:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while(li<t[2*i].size()&&ri<t[2*i+1].size()){
      |           ~~^~~~~~~~~~~~~~
currencies.cpp:19:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while(li<t[2*i].size()&&ri<t[2*i+1].size()){
      |                             ~~^~~~~~~~~~~~~~~~
currencies.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     }while(li<t[2*i].size())t[i].pb({t[2*i][li].f,{t[2*i][li].s.f,t[2*i][li].s.f}}),li++;
      |            ~~^~~~~~~~~~~~~~
currencies.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while(ri<t[2*i+1].size())t[i].pb({t[2*i+1][ri].f,{t[2*i+1][ri].s.f,t[2*i+1][ri].s.f}}),ri++;
      |           ~~^~~~~~~~~~~~~~~~
currencies.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=1;j<t[i].size();j++)t[i][j].s.s=t[i][j-1].s.s+t[i][j].s.f;
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'void hld(int, std::vector<long long int>, int, int)':
currencies.cpp:54:25: warning: operation on 'cnt' may be undefined [-Wsequence-point]
   54 |         a[cnt].s.f = cnt++;
      |                      ~~~^~
currencies.cpp:54:25: warning: operation on 'cnt' may be undefined [-Wsequence-point]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...