제출 #730825

#제출 시각아이디문제언어결과실행 시간메모리
730825groguTwo Currencies (JOI23_currencies)C++14
40 / 100
5009 ms69224 KiB
#define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll long long #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() using namespace std; #define maxn 200005 #define lg 20 int n,m,q; vector<int> g[maxn]; int in[maxn],out[maxn],st[lg][maxn],ti = 0; int in2[maxn],out2[maxn],ti2 = 0; pair<int,int> e[maxn]; vector<pll> v; void dfs1(int u,int p){ in[u] = ++ti; in2[u] = ++ti2; st[0][u] = p; for(int s : g[u]){ if(s==p) continue; dfs1(s,u); } out[u] = ++ti; out2[u] = ti2 - 1; } bool intree(int x,int y){return in2[y]<=in2[x]&&out2[y]>=out2[x];} int lca(int x,int y){ if(intree(x,y)) return y; if(intree(y,x)) return x; for(int j = lg-1;j>=0;j--){ if(!intree(x,st[j][y])) y = st[j][y]; } return st[0][y]; } struct segtree{ ll t[2*maxn]; segtree(){}; void init(int &v,int tl,int tr){ } ll sum(ll i){ ll ans = 0; for(; i>=0; i = (i&(i+1))-1) ans+=t[i]; return ans; } void upd(int v,int tl,int tr,int i,int x){ for(; i < 2*maxn;i = i|(i+1)) t[i]+=x; } ll sum(int v,int tl,int tr,int l,int r){ return sum(r) - sum(l-1); } } tsum,tcnt,tg; vector<ll> Q[maxn]; int L[maxn],R[maxn],MID[maxn]; int sta[maxn],en[maxn]; int au[maxn]; ll ag[maxn]; int ansl[maxn]; int ansr[maxn]; int rez[maxn]; int main(){ ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0); cin >> n >> m >> q; for(int i = 1;i<=n-1;i++){ ll x,y; cin >> x >> y; e[i] = {x,y}; g[x].pb(y); g[y].pb(x); } v.pb({-1,-1}); for(int i = 1;i<=m;i++){ ll j,w; cin >> j >> w; v.pb({w,j}); } sort(all(v)); dfs1(1,1); for(int j = 1;j<lg;j++) for(int i = 1;i<=n;i++) st[j][i] = st[j-1][st[j-1][i]]; for(int i = 1;i<=q;i++) cin >> sta[i] >> en[i] >> au[i] >> ag[i]; for(int i = 1;i<=q;i++){ L[i] = 0,R[i] = m; ansl[i] = m+1; ansr[i] = -llinf; rez[i] = 0; } bool change = 1; while(change){ for(int i = 0;i<=m;i++) Q[i].clear(); change = 0; for(int i = 1;i<=q;i++){ if(L[i]>R[i]) continue; change = 1; MID[i] = (L[i] + R[i])/2; Q[MID[i]].pb(i); } //here; for(int i = m;i>=0;i--){ if(v[i].fi!=-1){ ll x = e[v[i].sc].fi,y = e[v[i].sc].sc; if(st[0][y]==x) swap(x,y); ll w = v[i].fi; tg.upd(1,1,ti,in[x],1); tg.upd(1,1,ti,out[x],-1); } } //here; for(int i = 0;i<=m;i++){ if(v[i].fi!=-1){ ll x = e[v[i].sc].fi,y = e[v[i].sc].sc; if(st[0][y]==x) swap(x,y); ll w = v[i].fi; //cerr<<"w: "<<x<< " "<<y<< " "<<w<<endl; tsum.upd(1,1,ti,in[x],w); tsum.upd(1,1,ti,out[x],-w); tcnt.upd(1,1,ti,in[x],1); tcnt.upd(1,1,ti,out[x],-1); tg.upd(1,1,ti,in[x],-1); tg.upd(1,1,ti,out[x],1); } for(int j : Q[i]){ int x = sta[j],y = en[j]; int c = au[j]; ll d = ag[j]; int z = lca(x,y); //cerr<<"LCA: "<<x<< " "<<y<<" "<<z<<endl; ll cur = 0; int cntg = 0; if(z!=x&&z!=y){ cur = tsum.sum(1,1,ti,in[z]+1,in[x]) + tsum.sum(1,1,ti,in[z]+1,in[y]); cntg = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]); }else{ if(x==z) swap(x,y); cur = tsum.sum(1,1,ti,in[z]+1,in[x]); cntg = tg.sum(1,1,ti,in[z]+1,in[x]); } if(cur<=d){ ansr[j] = MID[j]; rez[j] = cntg; L[j] = MID[j] + 1; }else R[j] = MID[j] - 1; //if(j==8) cerr<<"j: "<<x<< " "<<y<< " "<<d<< " "<<cur<<endl; } Q[i].clear(); } for(int i = 0;i<=m;i++){ if(v[i].fi!=-1){ int x = e[v[i].sc].fi,y = e[v[i].sc].sc; if(st[0][y]==x) swap(x,y); ll w = v[i].fi; tsum.upd(1,1,ti,in[x],-w); tsum.upd(1,1,ti,out[x],w); tcnt.upd(1,1,ti,in[x],-1); tcnt.upd(1,1,ti,out[x],1); } } } for(int i = 1;i<=q;i++){ L[i] = 0,R[i] = m; } change = 1; while(change){ for(int i = 0;i<=m;i++) Q[i].clear(); change = 0; for(int i = 1;i<=q;i++){ if(L[i]>R[i]) continue; change = 1; MID[i] = (L[i] + R[i])/2; Q[MID[i]].pb(i); } //here; for(int i = m;i>=0;i--){ if(v[i].fi!=-1){ int x = e[v[i].sc].fi,y = e[v[i].sc].sc; if(st[0][y]==x) swap(x,y); ll w = v[i].fi; tg.upd(1,1,ti,in[x],1); tg.upd(1,1,ti,out[x],-1); } for(ll j : Q[i]){ int x = sta[j],y = en[j],c = au[j]; ll d = ag[j]; int z = lca(x,y); ll cur = 0; if(z!=x&&z!=y){ cur = tg.sum(1,1,ti,in[z]+1,in[x]) + tg.sum(1,1,ti,in[z]+1,in[y]); }else{ if(x==z) swap(x,y); cur = tg.sum(1,1,ti,in[z]+1,in[x]); } if(cur<=c){ ansl[j] = MID[j]; R[j] = MID[j] - 1; }else L[j] = MID[j] + 1; } Q[i].clear(); } for(int i = m;i>=0;i--){ if(v[i].fi!=-1){ ll x = e[v[i].sc].fi,y = e[v[i].sc].sc; if(st[0][y]==x) swap(x,y); ll w = v[i].fi; tg.upd(1,1,ti,in[x],-1); tg.upd(1,1,ti,out[x],1); } } } for(int i = 1;i<=q;i++){ if(ansl[i]>ansr[i]+1){ cout<<-1<<endl; continue; }else cout<<au[i] - rez[i]<<endl; } return 0; } /** 5 4 3 1 2 1 3 2 4 2 5 2 9 2 4 3 5 4 7 3 4 2 11 5 3 4 5 2 3 1 1 10 7 9 1 8 6 3 5 9 7 9 3 1 3 4 10 1 2 6 5 6 9 4 7 4 7 4 2 4 7 4 7 4 1 4 8 6 5 3 3 9 8 0 4 7 6 15 7 4 9 3 6 4 8 0 9 10 5 16 5 3 2 4 2 8 4 3 6 1 3 3 8 7 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 4 4 3 7 2 10 5 2 4 1 4 4 5 6 6 3 7 69 7 1 5 55 3 1 6 8 8 2 5 45 4 6 4 45 6 1 3 33 2 1 0 19 3 7 2 31 7 1 2 31 7 2 4 58 8 3 5 63 **/

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

currencies.cpp: In function 'int main()':
currencies.cpp:95:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
   95 |         ansr[i] = -llinf;
      |                   ^
currencies.cpp:113:20: warning: unused variable 'w' [-Wunused-variable]
  113 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:134:21: warning: unused variable 'c' [-Wunused-variable]
  134 |                 int c = au[j];
      |                     ^
currencies.cpp:187:20: warning: unused variable 'w' [-Wunused-variable]
  187 |                 ll w = v[i].fi;
      |                    ^
currencies.cpp:193:20: warning: unused variable 'd' [-Wunused-variable]
  193 |                 ll d = ag[j];
      |                    ^
currencies.cpp:213:20: warning: unused variable 'w' [-Wunused-variable]
  213 |                 ll w = v[i].fi;
      |                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...