Submission #710240

#TimeUsernameProblemLanguageResultExecution timeMemory
710240victor_gaoDesignated Cities (JOI19_designated_cities)C++17
100 / 100
498 ms73724 KiB
//#pragma GCC optimize("Ofast,unroll-loops,O3") //#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native") #include<bits/stdc++.h> //#include<bits/extc++.h> //#pragma pack(1) #define fast ios::sync_with_stdio(0); cin.tie(0); #define int long long #define pii pair<int,int> #define x first #define y second #define N 200015 using namespace std; //using namespace __gnu_pbds; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset; //typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set; int n,dp[N],ans[N],mx[N],len[N],pos[N],total=0,s; int fa[N],cost[N],in[N],out[N],dep[N],t=0; bool vis[N]; vector<pair<int,pii> >g[N]; vector<int>path; void dfs1(int p,int lp){ pos[p]=p; for (auto [i,c]:g[p]){ if (i!=lp){ dfs1(i,p); dp[p]=dp[p]+dp[i]+c.y; mx[p]=max(mx[p],mx[i]+c.x); } } } void dfs2(int p,int lp,int val){ dp[p]=(dp[p]+dp[lp]+val); ans[1]=min(ans[1],total-dp[p]); if (ans[2]>total-dp[p]-len[p]){ ans[2]=total-dp[p]-len[p]; s=p; } for (auto [i,c]:g[p]){ if (i!=lp){ dp[p]=dp[p]-dp[i]-c.y; dfs2(i,p,c.x); dp[p]=dp[p]+dp[i]+c.y; } } dp[p]=(dp[p]-dp[lp]-val); } void dfs3(int p,int lp,int up){ int mx1=0,mx2=0; len[p]=max(mx[p],up); for (auto [i,c]:g[p]){ if (i!=lp){ mx2=max(mx2,mx[i]+c.x); if (mx2>mx1) swap(mx1,mx2); } } for (auto [i,c]:g[p]){ if (i!=lp){ int use=(mx[i]+c.x==mx1) ? mx2 : mx1; dfs3(i,p,max(up,use)+c.y); } } } void dfs4(int p,int lp,int cs){ cost[p]=cs; fa[p]=lp; in[p]=++t; dep[p]=dep[lp]+cs; path.push_back(p); for (auto [i,c]:g[p]){ if (i!=lp) dfs4(i,p,c.x); } out[p]=t; } struct segtree{ pii seg[4*N]; int tag[4*N]; void add_tag(int i,int val){ seg[i].x+=val; tag[i]+=val; } void push(int i){ if (tag[i]){ add_tag(2*i,tag[i]); add_tag(2*i+1,tag[i]); tag[i]=0; } } void build(int l,int r,int i){ if (l==r){ seg[i]={dep[path[l-1]],path[l-1]}; return; } int mid=(l+r)>>1; build(l,mid,2*i); build(mid+1,r,2*i+1); seg[i]=max(seg[2*i],seg[2*i+1]); } void modify(int l,int r,int i,int ll,int rr,int val){ if (ll<=l&&rr>=r){ add_tag(i,val); return; } int mid=(l+r)>>1; push(i); if (rr<=mid) modify(l,mid,2*i,ll,rr,val); else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,val); else { modify(l,mid,2*i,ll,rr,val); modify(mid+1,r,2*i+1,ll,rr,val); } seg[i]=max(seg[2*i],seg[2*i+1]); } }seg; void walk(int a){ while (!vis[a]){ vis[a]=1; seg.modify(1,n,1,in[a],out[a],-cost[a]); a=fa[a]; } } signed main(){ fast cin>>n; for (int i=0;i<=n;i++) ans[i]=1e18; for (int i=1;i<n;i++){ int a,b,c,d; cin>>a>>b>>c>>d; total=(total+c+d); g[a].push_back({b,{c,d}}); g[b].push_back({a,{d,c}}); } dfs1(1,0); dfs3(1,0,0); dfs2(1,0,0); dfs4(s,0,0); seg.build(1,n,1); vis[s]=1; for (int i=2;i<=n;i++){ pii now=seg.seg[1]; if (i>2) ans[i]=ans[i-1]-now.x; walk(now.y); } int q; cin>>q; while (q--){ int c; cin>>c; cout<<ans[c]<<'\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...