Submission #127165

#TimeUsernameProblemLanguageResultExecution timeMemory
127165wilwxkDesignated Cities (JOI19_designated_cities)C++14
100 / 100
815 ms78360 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=2e5+5; vector<tuple<int, ll, ll> > g[MAXN]; pair<ll, int> mprof[MAXN][2]; pair<ll, int> seg[MAXN*4]; ll lz[MAXN*4]; ll dp[MAXN], respf[MAXN], ppai[MAXN], somaf; int tini[MAXN], tfim[MAXN], tcara[MAXN], pai[MAXN]; bool marc[MAXN]; int n, q, raiz, contt; void melhora(int cur, pair<ll, int> val) { if(val.first>=mprof[cur][0].first) { mprof[cur][1]=mprof[cur][0]; mprof[cur][0]=val; } else if(val.first>mprof[cur][1].first) { mprof[cur][1]=val; } } void predfs(int cur, int p) { mprof[cur][0]={0, cur}; for(auto aresta : g[cur]) { int viz; ll peso, rpeso; tie(viz, peso, rpeso)=aresta; if(viz==p) continue; predfs(viz, cur); dp[cur]+=dp[viz]+rpeso; melhora(cur, {mprof[viz][0].first+peso, mprof[viz][0].second}); } tfim[cur]=contt; } void gira(int cur, int p) { respf[1]=max(respf[1], dp[cur]); if(dp[cur]+mprof[cur][0].first>respf[2]) { respf[2]=dp[cur]+mprof[cur][0].first; raiz=cur; } // printf("dp[%d]= %lld // mprof[%d][0]= %lld, %d\n", cur, dp[cur], cur, mprof[cur][0].first, mprof[cur][0].second); for(auto aresta : g[cur]) { int viz; ll peso, rpeso; tie(viz, peso, rpeso)=aresta; if(viz==p) continue; ll dpc=dp[cur], dpv=dp[viz]; auto mprofc0=mprof[cur][0], mprofc1=mprof[cur][1]; auto mprofv0=mprof[viz][0], mprofv1=mprof[viz][1]; dp[cur]-=(dp[viz]+rpeso); dp[viz]+=(dp[cur]+peso); if(mprof[cur][0].second==mprof[viz][0].second) mprof[cur][0]=mprof[cur][1]; melhora(viz, {mprof[cur][0].first+rpeso, mprof[cur][0].second}); gira(viz, cur); dp[cur]=dpc; dp[viz]=dpv; mprof[cur][0]=mprofc0; mprof[cur][1]=mprofc1; mprof[viz][0]=mprofv0; mprof[viz][1]=mprofv1; } } void refresh(int sind, int ini, int fim) { seg[sind].first+=lz[sind]; if(ini==fim) { lz[sind]=0; seg[sind].second=tcara[ini]; return; } int e=sind*2; int d=e+1; lz[e]+=lz[sind]; lz[d]+=lz[sind]; lz[sind]=0; } void update(int sind, int ini, int fim, int qini, int qfim, ll val) { refresh(sind, ini, fim); if(qini>fim||qfim<ini) return; if(qini<=ini&&qfim>=fim) { lz[sind]+=val; refresh(sind, ini, fim); return; } int m=(ini+fim)/2; int e=sind*2; int d=e+1; update(e, ini, m, qini, qfim, val); update(d, m+1, fim, qini, qfim, val); seg[sind]=max(seg[e], seg[d]); } void dfs(int cur, int p, ll d) { tini[cur]=++contt; for(auto aresta : g[cur]) { int viz; ll peso, rpeso; tie(viz, peso, rpeso)=aresta; if(viz==p) continue; dfs(viz, cur, d+peso); pai[viz]=cur; ppai[viz]=peso; } tfim[cur]=contt; tcara[tini[cur]]=cur; update(1, 1, n, tini[cur], tini[cur], d); // printf("update %d +%lld\n", tini[cur], d); } void pinta(int cur) { while(!marc[cur]) { marc[cur]=1; update(1, 1, n, tini[cur], tfim[cur], -ppai[cur]); cur=pai[cur]; } } int main() { scanf("%d", &n); for(int i=1; i<n; i++) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); g[a].push_back({b, c, d}); g[b].push_back({a, d, c}); somaf+=c; somaf+=d; } predfs(1, 1); gira(1, 1); dfs(raiz, raiz, 0); marc[raiz]=1; pinta(seg[1].second); // for(int i=1; i<=n; i++) printf("%d >> %d %d >> %lld %d\n", i, tini[i], tfim[i], ppai[i], pai[i]); for(int i=3; i<=n; i++) { respf[i]=respf[i-1]+seg[1].first; int cara=seg[1].second; pinta(cara); // printf("%d usa %d\n", i, cara); } scanf("%d", &q); while(q--) { int val; scanf("%d", &val); printf("%lld\n", somaf-respf[val]); } }

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:121:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:143:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int val; scanf("%d", &val);
            ~~~~~^~~~~~~~~~~~
#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...