Submission #380462

#TimeUsernameProblemLanguageResultExecution timeMemory
380462i_am_noobDesignated Cities (JOI19_designated_cities)C++17
7 / 100
693 ms76140 KiB
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma") #include<bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") using namespace std; #define ll long long #define int ll #define ull unsigned long long #define ld long double #define rep(a) rep1(i,a) #define rep1(i,a) rep2(i,0,a) #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++) #define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--) #define all(a) a.begin(),a.end() #define pii pair<int,int> #define pb push_back //#define inf 1010000000 #define inf 4000000000000000000 #define eps 1e-9 #define sz(a) ((int)a.size()) #define pow2(x) (1ll<<(x)) #define ceiling(a,b) (((a)+(b)-1)/(b)) #ifdef i_am_noob #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...);} #else #define bug(...) 826 #endif inline char readchar(){ const int maxn=1000000; static char buf[maxn],*p=buf,*q=buf; if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF; else return *p++; } inline int readint(){ int c=readchar(),x=0,neg=0; while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar(); if(c=='-') neg=1,c=readchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar(); return neg?-x:x; } const int Mod=1000000007,Mod2=998244353; const int MOD=Mod; const int maxn=200005; //i_am_noob int n,par[maxn],up[maxn],down[maxn],arr[maxn],dp[maxn],dpid[maxn],sumd,sumu,minid,k1,k2,lpos[maxn],rpos[maxn],rev[maxn]; int val[maxn*4],maxid[maxn*4],tag[maxn*4]; int ans[maxn]; vector<pii> adj[maxn]; bool vis[maxn]; void dfs1(int u, int p){ par[u]=p; for(auto& [v,w]: adj[u]){ if(v==p) up[u]=w,sumu+=w; else{ dfs1(v,u); sumd+=w; down[v]=w; } } } void dfs2(int u, int p, int curd, int curu){ arr[u]=0; dp[u]=0; int cnt=0; for(auto& [v,w]: adj[u]) if(v!=p){ dfs2(v,u,curd+w,curu+up[v]); arr[u]+=arr[v]+w; cnt++; if(dp[v]+w>dp[u]) dp[u]=dp[v]+w,dpid[u]=dpid[v]; } if(!cnt) dpid[u]=u; ans[1]=min(ans[1],sumd-curd+curu); if(cnt>=2){ vector<pii> vec; for(auto& [v,w]: adj[u]) if(v!=p) vec.pb({dp[v]+w,dpid[v]}); sort(all(vec)); reverse(all(vec)); int tmp=sumd-curd-(vec[0].first+vec[1].first)+curu; if(tmp<ans[2]) ans[2]=tmp,minid=u,k1=vec[0].second,k2=vec[1].second; } } void dfs3(int u, int p, int cur){ int cnt=0; for(auto& [v,w]: adj[u]) if(v!=p) { cnt++; dfs3(v,u,cur+w); } if(!cnt) arr[lpos[u]]=cur; else arr[lpos[u]]=-inf; } void dfs4(int u, int p){ static int t=0; lpos[u]=t++; rev[t-1]=lpos[u]; for(auto& [v,w]: adj[u]) if(v!=p) dfs4(v,u); rpos[u]=t-1; } void pull(int k){ val[k]=max(val[k<<1],val[k<<1|1]); if(val[k]==val[k<<1]) maxid[k]=maxid[k<<1]; else maxid[k]=maxid[k<<1|1]; } void push(int k, int l, int r){ if(l!=r){ val[k<<1]+=tag[k],val[k<<1|1]+=tag[k]; tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k]; } tag[k]=0; } void build(int k, int l, int r){ if(l==r){ val[k]=arr[l]; maxid[k]=l; return; } int mid=l+r>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); pull(k); } void modify(int k, int l, int r, int ql, int qr, int x){ if(ql>r||qr<l) return; if(ql<=l&&qr>=r){ val[k]+=x,tag[k]+=x; return; } int mid=l+r>>1; push(k,l,r); modify(k<<1,l,mid,ql,qr,x),modify(k<<1|1,mid+1,r,ql,qr,x); pull(k); } void modify(int u){ for(int i=u; !vis[i]; i=par[i]){ bug(i,down[i]); vis[i]=1; modify(1,0,n-1,lpos[i],rpos[i],-down[i]); } } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); #ifdef i_am_noob freopen("input1.txt","r",stdin); freopen("output1.txt","w",stdout); freopen("output2.txt","w",stderr); #endif cin >> n; rep(n-1){ int u,v,w1,w2; cin >> u >> v >> w1 >> w2; u--,v--; adj[u].pb({v,w1}),adj[v].pb({u,w2}); } dfs1(0,-1); ans[1]=ans[2]=inf; dfs2(0,-1,0,0); bug(minid); dfs1(minid,-1); dfs4(minid,-1); dfs3(minid,-1,0); vis[minid]=1; build(1,0,n-1); bug(k1,k2); bug(val[1],rev[maxid[1]]); modify(k1),modify(k2); bug(val[1],rev[maxid[1]]); rep2(i,3,n+1){ if(ans[i-1]==0){ ans[i]=0; continue; } int u=rev[maxid[1]]; ans[i]=ans[i-1]-val[1]; bug(u,val[1]); modify(u); } int q; cin >> q; while(q--){ int k; cin >> k; cout << ans[k] << "\n"; } return 0; }

Compilation message (stderr)

designated_cities.cpp: In function 'void build(long long int, long long int, long long int)':
designated_cities.cpp:127:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     int mid=l+r>>1;
      |             ~^~
designated_cities.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, long long int)':
designated_cities.cpp:138:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     int mid=l+r>>1;
      |             ~^~
designated_cities.cpp: In function 'void modify(long long int)':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:146:9: note: in expansion of macro 'bug'
  146 |         bug(i,down[i]);
      |         ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:169:5: note: in expansion of macro 'bug'
  169 |     bug(minid);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:175:5: note: in expansion of macro 'bug'
  175 |     bug(k1,k2);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:176:5: note: in expansion of macro 'bug'
  176 |     bug(val[1],rev[maxid[1]]);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:178:5: note: in expansion of macro 'bug'
  178 |     bug(val[1],rev[maxid[1]]);
      |     ^~~
designated_cities.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
designated_cities.cpp:186:9: note: in expansion of macro 'bug'
  186 |         bug(u,val[1]);
      |         ^~~
#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...