제출 #487452

#제출 시각아이디문제언어결과실행 시간메모리
487452phamhoanghiepDesignated Cities (JOI19_designated_cities)C++17
100 / 100
919 ms96600 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define int long long typedef pair<int,int> ii; typedef pair<int,ii> iii; const int maxn=2e5+5; vector<iii> AdjList[maxn]; int n; int cost[maxn]; int res[maxn]; int sum; int ans[maxn]; int ans1[maxn]; int path[maxn]; bool used[maxn]; pair<int,int> par[maxn]; void prep(int s=1, int p=-1) { ////cout<<"prep "<<s<<endl; for(iii tmp: AdjList[s]) { int u=tmp.fi; if(u==p) continue; int w=tmp.se.se; cost[1]+=w; prep(u,s); } } void dfs(int s=1, int p=-1) { ////cout<<"dfs "<<s<<endl; for(iii tmp: AdjList[s]) { int u=tmp.fi; if(u==p) continue; int fw=tmp.se.fi; int bw=tmp.se.se; // currently bw cost[u]=cost[s]+fw-bw; dfs(u,s); } } int in[maxn]; int out[maxn]; int rev[maxn]; int up[maxn][20]; int curt=0; bool ancestor(int a, int b) { if(!a) return true; if(!b) return false; return in[a]<=in[b]&&out[a]>=out[b]; } void dfs2(int s, int p=0) { ////cout<<"dfs2 "<<s<<endl; in[s]=++curt; //cout<<"in "<<s<<" = "<<in[s]<<endl; rev[in[s]]=s; up[s][0]=p; for(int i=1 ; i<20 ; i++) { up[s][i]=up[up[s][i-1]][i-1]; ////cout<<"up "<<s<<" "<<i<<" = "<<up[s][i]<<endl; } for(iii tmp: AdjList[s]) { int u=tmp.fi; if(u==p) continue; int fw=tmp.se.fi; path[u]=path[s]+fw; par[u]=ii(s,fw); ////cout<<"par "<<u<<" = "<<s<<" "<<fw<<endl; ////cout<<"u = "<<u<<endl; dfs2(u,s); } out[s]=curt; //cout<<"out "<<s<<" = "<<out[s]<<endl; } int lca(int u, int v) { ////cout<<"lca "<<u<<" "<<v<<" = "<<endl; if(ancestor(u,v)) return u; if(ancestor(v,u)) return v; for(int i=20 ; i>0 ; i--) { ////cout<<"up "<<u<<" "<<i<<" = "<<up[u][i]<<endl; if(!ancestor(up[u][i],v)) u=up[u][i]; } ////cout<<up[u][0]<<endl; return up[u][0]; } // segment tree pair<int,int> st[maxn*4]; // max int lz[maxn*4]; void build(int id=1, int tl=1, int tr=n) { ////cout<<"build "<<tl<<" "<<tr<<endl; if(tl==tr) { st[id]=make_pair(path[rev[tl]],tl); lz[id]=0; ////cout<<"st "<<id<<" = "<<st[id].first<<" "<<st[id].second<<'\n'; return; } int mid=(tl+tr)/2; build(id*2,tl,mid); build(id*2+1,mid+1,tr); lz[id]=0; st[id]=max(st[id*2],st[id*2+1]); ////cout<<"st "<<tl<<" "<<tr<<" = "<<st[id].first<<" "<<st[id].second<<'\n'; } void do_lazy(int id, int tl, int tr) { if(!lz[id]) return; if(tl!=tr) { lz[id*2]+=lz[id]; lz[id*2+1]+=lz[id]; } st[id].first-=lz[id]; lz[id]=0; return; } void upd(int id, int tl, int tr, int l, int r, int sub) { ////cout<<"update "<<id<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl; do_lazy(id,tl,tr); if(tl>r||tr<l) return; if(l<=tl&&tr<=r) { lz[id]+=sub; do_lazy(id,tl,tr); return; } int mid=(tl+tr)/2; upd(id*2,tl,mid,l,r,sub); upd(id*2+1,mid+1,tr,l,r,sub); st[id]=max(st[id*2],st[id*2+1]); ////cout<<"st "<<tl<<" "<<tr<<" = "<<st[id].first<<" "<<st[id].second<<endl; } void sub(int v) { while(v) { ii tmp=par[v]; int w=tmp.second; int p=tmp.first; if(used[v]) break; used[v]=1; upd(1,1,n,in[v],out[v],w); //cout<<"update "<<v<<" "<<w<<endl; v=p; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1 ; i<n ; i++) { int a,b,c,d; cin>>a>>b>>c>>d; AdjList[a].push_back(iii(b,ii(c,d))); // forward then backward AdjList[b].push_back(iii(a,ii(d,c))); sum+=c; sum+=d; } prep(); dfs(); int root=1; int mx_cost=cost[1]; for(int i=2 ; i<=n ; i++) { if(cost[i]>mx_cost) { root=i; mx_cost=cost[i]; } } dfs2(root); ////cout<<"root = "<<root<<endl; build(); ////cout<<"cost "<<root<<" = "<<cost[root]<<endl; pair<int,int> mn=st[1]; int id1=mn.second; int val1=mn.first; int root1=rev[id1]; curt=0; par[root]=ii(0,0); path[root]=0; dfs2(root); build(); ans[1]=cost[root]; //cout<<"root = "<<root<<endl; //cout<<"sum = "<<sum<<endl; //cout<<"ans "<<1<<" = "<<ans[1]<<endl; for(int i=1 ; i<=n ; i++) used[i]=0; for(int i=2 ; i<=n ; i++) { pair<int,int> mn=st[1]; int id=mn.second; int val=mn.first; int v=rev[id]; //cout<<"val "<<val<<endl; //cout<<"v = "<<v<<endl; ////cout<<endl<<"v = "<<v<<endl; ////cout<<"mn = "<<val<<" "<<id<<endl; ans[i]=ans[i-1]+val; //cout<<"ans "<<i<<" = "<<ans[i]<<endl<<endl; sub(v); } curt=0; par[root1]=ii(0,0); path[root1]=0; dfs2(root1); build(); ans1[1]=cost[root1]; //cout<<"root = "<<root<<endl; //cout<<"sum = "<<sum<<endl; //cout<<"ans "<<1<<" = "<<ans[1]<<endl; for(int i=1 ; i<=n ; i++) used[i]=0; for(int i=2 ; i<=n ; i++) { pair<int,int> mn=st[1]; int id=mn.second; int val=mn.first; int v=rev[id]; //cout<<"val "<<val<<endl; //cout<<"v = "<<v<<endl; ////cout<<endl<<"v = "<<v<<endl; ////cout<<"mn = "<<val<<" "<<id<<endl; ans1[i]=ans1[i-1]+val; //cout<<"ans "<<i<<" = "<<ans[i]<<endl<<endl; sub(v); } int q; cin>>q; while(q--) { int x; cin>>x; ans[x]=max(ans[x],ans1[x]); cout<<sum-ans[x]<<'\n'; } }

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

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:165:9: warning: unused variable 'val1' [-Wunused-variable]
  165 |     int val1=mn.first;
      |         ^~~~
#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...