Submission #127154

#TimeUsernameProblemLanguageResultExecution timeMemory
127154wilwxkDesignated Cities (JOI19_designated_cities)C++14
39 / 100
2053 ms56568 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]; bool marc[MAXN]; ll dp[MAXN]; ll respf[MAXN], somaf; int n, q, raiz; 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 recalc(int cur, int p) { dp[cur]=0; mprof[cur][0]=mprof[cur][1]={0, cur}; for(auto aresta : g[cur]) { int viz; ll peso, rpeso; tie(viz, peso, rpeso)=aresta; if(viz==p) continue; recalc(viz, cur); dp[cur]+=dp[viz]+rpeso; if(!marc[viz]) melhora(cur, {mprof[viz][0].first+peso, mprof[viz][0].second}); else melhora(cur, {mprof[viz][0].first, mprof[viz][0].second}); } } void dfs(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}); dfs(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 pinta(int cur, int p, int alvo) { if(cur==alvo) marc[cur]=1; for(auto aresta : g[cur]) { int viz; ll peso, rpeso; tie(viz, peso, rpeso)=aresta; if(viz==p) continue; pinta(viz, cur, alvo); if(marc[viz]) marc[cur]=1; } } ll responde(int val) { if(respf[val]!=0) return respf[val]; respf[val]=responde(val-1); respf[val]+=mprof[raiz][0].first; int cara=mprof[raiz][0].second; pinta(raiz, raiz, cara); recalc(raiz, raiz); return respf[val]; } 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; } recalc(1, 1); dfs(1, 1); recalc(raiz, raiz); pinta(raiz, raiz, mprof[raiz][0].second); recalc(raiz, raiz); scanf("%d", &q); while(q--) { int val; scanf("%d", &val); printf("%lld\n", somaf-responde(val)); } }

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:91: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:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:104: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...