제출 #465143

#제출 시각아이디문제언어결과실행 시간메모리
465143nathanlee726Designated Cities (JOI19_designated_cities)C++14
100 / 100
516 ms54472 KiB
//#include<i_am_noob_orz> #include<bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define int ll #define ull unsigned long long #define pii pair<int,int> #define X first #define Y second #define mod ((ll)1e9+7) #define pb push_back #define mp make_pair #define abs(x) ((x)>0?(x):(-(x))) #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define memres(a) memset(a,0,sizeof(a)) #define all(a) a.begin(),a.end() #define sz(a) ((int)a.size()) #define ceiling(a,b) (((a)+(b)-1)/(b)) #define endl '\n' #define bit_count(x) __builtin_popcountll((x)) #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define jimmy_is_kind false typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree; //#define LOCAL #ifdef LOCAL #define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);} #define IOS() #else #define IOS() ios_base::sync_with_stdio(0), cin.tie(0) #define endl '\n' #define bug(...) #endif int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);} int sub(int a,int b){return(a<b?a+mod-b:a-b);} int po(int a,int b){ if(b==0)return 1; if(b==1)return(a%mod); int tem=po(a,b/2); if(b&1)return(((tem*tem)%mod)*a)%mod; else return(tem*tem)%mod; } int GCD(int a,int b){ int x=0; int ra,rb; while(a&&b){ if(((a&1)==0)&&((b&1)==0)){ a>>=1,b>>=1,x++; } else if((a^b)&1){ if(a&1)b>>=1; else a>>=1; } else{ ra=abs(a-b),rb=min(a,b); a=ra,b=rb; } } return max(a,b)<<x; } int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);} vector<pair<int,pii> > g[200010]; vector<int> v; int n,p,s=0,fa[200010],o[200010],vl[200010],mv[200010],qr[200010],so[200010],in[200010],val[200010],mvl[200010]; pii vv[200010],rt; bool rd[200010]; void dfs(int p,int f){ fa[p]=f; for(pair<int,pii> pi:g[p]){ if(pi.X==f)continue; dfs(pi.X,p); } } int dfs1(int p,int f){ int re=-1; for(pair<int,pii> pi:g[p]){ if(pi.X==f)continue; int tr=dfs1(pi.X,p)+pi.Y.X; if(tr<0)continue; if(re==-1){ re=tr; } else{ if(tr>re)swap(tr,re); v.pb(tr); } } if(rd[p]){ if(re>=0)v.pb(re); return -1e16; } else{ if(re<0)return 0; return re; } } void dfs2(int p,int f){ for(pair<int,pii> pi:g[p]){ if(pi.X==f)continue; dfs2(pi.X,p); vl[p]+=(vl[pi.X]+pi.Y.Y); mv[pi.X]=vl[pi.X]+pi.Y.Y; } } int dfs3(int p,int f){ int re=vl[p]; for(pair<int,pii> pi:g[p]){ if(pi.X==f)continue; vl[pi.X]+=vl[p]-mv[pi.X]+pi.Y.X; re=max(re,dfs3(pi.X,p)); } return re; } pii dfs4(int p,int f){ pii tp={-1,-1},tpp={-1,-1}; for(pair<int,pii> pi:g[p]){ if(pi.X==f)continue; pii tr=dfs4(pi.X,p); tr.X+=pi.Y.X; if(tr.X>=tp.X){ swap(tp.X,tp.Y); swap(tpp.X,tpp.Y); tp.X=tr.X; tpp.X=tr.Y; } else if(tr.X>=tp.Y){ tp.Y=tr.X; tpp.Y=tr.Y; } } if(tp.X==-1){ return {0,p}; } else if(tp.Y==-1){ if(o[2]>vl[p]-tp.X){ o[2]=vl[p]-tp.X; rt={p,tpp.X}; } return {tp.X,tpp.X}; } else{ if(o[2]>vl[p]-tp.X-tp.Y){ o[2]=vl[p]-tp.X-tp.Y; rt={tpp.X,tpp.Y}; bug(p,vl[p],tp.X,tp.Y,tpp.X,tpp.Y); } return {tp.X,tpp.X}; } } void solve1(){ memres(vl); memres(mv); dfs2(0,-1); int x=dfs3(0,-1); o[1]=s-x; } void solve2(){ o[2]=1e16; F(n)vl[i]=s-vl[i]; dfs4(0,-1); } signed main(){ IOS(); cin>>n; F(n-1){ int x,y,a,b; cin>>x>>y>>a>>b; s+=(a+b); --x,--y; g[x].pb({y,{a,b}}); g[y].pb({x,{b,a}}); in[x]++,in[y]++; } int q; cin>>q; F(q)cin>>qr[i]; solve1(); solve2(); int p=rt.X,pp=rt.Y; bug(p,pp); dfs(p,-1); int tp=pp; while(tp!=-1){ if(fa[tp]!=-1)so[fa[tp]]=tp; rd[tp]=1; tp=fa[tp]; } dfs1(p,-1); int ct=0; F(n)if(sz(g[i])==1)ct++; sort(all(v)); int ms=0; for(int i=ct-1;i>=2;i--){ ms+=v[ct-1-i]; bug(v[ct-1-i],sz(v),ct); o[i]=ms; } F(q){ if(qr[i]>=ct)cout<<0<<endl; else cout<<o[qr[i]]<<endl; } return 0; }
#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...