Submission #173366

#TimeUsernameProblemLanguageResultExecution timeMemory
173366ZwariowanyMarcinDesignated Cities (JOI19_designated_cities)C++14
100 / 100
1298 ms38140 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define ss(x) (int) x.size() #define pb push_back #define ll long long #define cat(x) cerr << #x << " = " << x << endl #define FOR(i, n) for(int i = 0; i < n; ++i) using namespace std; const int nax = 2e5 + 111; int n, nn; int a, b, c, d; vector <pair<int,int>> v[nax]; ll all; ll ans[nax]; int died[nax]; int siz[nax]; void dfs(int u, int p) { siz[u] = 1; nn++; for(auto it : v[u]) if(it.fi != p && !died[it.fi]) { dfs(it.fi, u); siz[u] += siz[it.fi]; } } int daj(int u, int p) { for(auto it : v[u]) if(it.fi != p && !died[it.fi] && nn <= 2 * siz[it.fi]) return daj(it.fi, u); return u; } ll oblicz(int u, int p) { ll sum = 0; for(auto it : v[u]) { if(it.fi == p) sum += it.se; else if(!died[it.fi]) sum += oblicz(it.fi, u); } return sum; } ll dp[nax]; void makedp(int u, int p) { dp[u] = 0; for(auto it : v[u]) if(it.fi != p && !died[it.fi]) { makedp(it.fi, u); dp[u] = max(dp[u], dp[it.fi] + it.se); } } vector <pair<ll, int>> vec; void go(int u, int p, ll cost = 0, int anc = -1) { tuple <ll, int, int> best = make_tuple(-1, 0, 0); for(auto it : v[u]) if(it.fi != p && !died[it.fi]) best = max(best, make_tuple(dp[it.fi] + it.se, it.fi, it.se)); if(get<0> (best) != -1) go(get<1> (best), u, cost + get<2> (best), (anc == -1 ? get<1> (best) : anc)); else vec.pb(mp(cost, anc)); for(auto it : v[u]) if(it.fi != p && !died[it.fi] && it.fi != get<1> (best)) go(it.fi, u, it.se, (anc == -1 ? it.fi : anc)); } ll o[nax]; void solve(int u) { makedp(u, 0); go(u, 0); sort(vec.begin(), vec.end()); reverse(vec.begin(), vec.end()); ll pref = 0; for(int i = 0; i < ss(vec); ++i) { pref += vec[i].fi; ans[i + 2] = max(ans[i + 2], o[u] + pref); } int h = 0; while(h < ss(vec) && vec[h].se == vec[0].se) h++; if(h < ss(vec)) { ll cnt = vec[h].fi + vec[0].fi; ans[2] = max(ans[2], cnt + o[u]); int ile = 2; for(int i = 1; i < ss(vec); ++i) { if(i == h) continue; ile++; cnt += vec[i].fi; ans[ile] = max(ans[ile], cnt + o[u]); } } vec.clear(); } void pro(int u, int p, ll cost) { ll k = 0; for(auto it : v[u]) { if(it.fi != p) ; else k = it.se; } cost -= k; o[u] = cost; ans[1] = max(ans[1], o[u]); for(auto it : v[u]) if(it.fi != p) pro(it.fi, u, cost + it.se); } void decomp(int u) { nn = 0; dfs(u, 0); int c = daj(u, 0); solve(c); died[c] = 1; for(auto it : v[c]) if(!died[it.fi]) decomp(it.fi); } int main() { scanf("%d", &n); for(int i = 1; i < n; ++i) { scanf("%d %d %d %d", &a, &b, &c, &d); v[a].pb(mp(b, c)); v[b].pb(mp(a, d)); all += c + d; } o[1] = oblicz(1, 0); pro(1, 0, o[1]); decomp(1); for(int i = 1; i <= n; ++i) ans[i] = max(ans[i], ans[i - 1]); int q; scanf("%d", &q); while(q--) { scanf("%d", &a); printf("%lld\n", all - ans[a]); } return 0; }

Compilation message (stderr)

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