Submission #223968

#TimeUsernameProblemLanguageResultExecution timeMemory
223968osaaateiasavtnlDesignated Cities (JOI19_designated_cities)C++14
23 / 100
2080 ms59056 KiB
#include<bits/stdc++.h> using namespace std; #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcount #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int LG = 20, N = 2e5 + 7; const ll INF = 1e18; vector <ii> g[N]; int n; bool used[N], centr[N]; int cnt[N]; void calc(int u, int p) { cnt[u] = 1; used[u] = 1; for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p && !centr[v]) { calc(v, u); cnt[u] += cnt[v]; } } } int get(int u, int p, int all) { int mx = -1; for (auto e : g[u]) { int v = e.f; if (v != p && !centr[v]) { if (mx == -1 || cnt[mx] < cnt[v]) mx = v; } } if (mx == -1 || cnt[mx] * 2 <= all) return u; else return get(mx, u, all); } ll out[N], sum[N]; void calc_sum(int u, int p) { sum[u] = 0; for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p && !centr[v]) { calc_sum(v, u); sum[u] += sum[v] + c; } } } void add_out(int u, int p, ll x) { out[u] += x; for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p && !centr[v]) { add_out(v, u, x); } } } vector <ii> tree[N]; void build(int u, int p) { tree[u].clear(); for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p && !centr[v]) { tree[u].app(mp(v, c)); build(v, u); } } } int to[N]; ll h[N]; void ladder(int u, ll cur, ll &sum) { h[u] = cur; to[u] = -1; for (auto e : tree[u]) { ladder(e.f, cur + e.s, sum); sum += e.s; h[u] = max(h[u], h[e.f]); if (to[u] == -1 || h[to[u]] < h[e.f]) to[u] = e.f; } } void print(int u, int ded, ll cur, vector <pair <ll, int> > &a, bool root) { if (tree[u].empty()) a.app(mp(cur, ded)); else a.app(mp(0, ded)); for (auto e : tree[u]) { int d = ded; if (root) d = e.f; ll c = cur; if (to[u] != e.f) c = 0; c += e.s; print(e.f, d, c, a, 0); } } ll ans[N]; void solve(int c) { build(c, c); ll sum = 0; ladder(c, 0, sum); vector <pair <ll, int> > a; print(c, c, 0, a, 1); sort(all(a)); reverse(all(a)); ans[1] = min(ans[1], out[c] + sum); int l = -1; for (int i = 1; i < a.size(); ++i) { if (a[i].s != a[0].s) { l = i; break; } } sum -= a[0].f; for (int i = 1; i < a.size(); ++i) { sum -= a[i].f; if (l <= i) { ans[i + 1] = min(ans[i + 1], out[c] + sum); } else { ans[i + 1] = min(ans[i + 1], out[c] + sum + a[i].f - a[l].f); } } } map <ii, int> d; int edge(int u, int v) { return d[mp(u, v)]; } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n; for (int i = 0; i < n - 1; ++i) { int u, v, a, b; cin >> u >> v >> a >> b; g[u].app(mp(v, a)); g[v].app(mp(u, b)); d[mp(u,v)] = a; d[mp(v,u)] = b; } for (int i = 0; i < N; ++i) ans[i] = INF; for (int t = 0; t < LG; ++t) { memset(used, 0, sizeof used); for (int i = 1; i <= n; ++i) { if (!used[i] && !centr[i]) { calc(i, i); int c = get(i, i, cnt[i]); solve(c); calc_sum(c, c); for (auto e : g[c]) { int v = e.f, cost = e.s; if (!centr[v]) { add_out(v, c, sum[c] - sum[v] - cost + edge(v, c)); } } centr[c] = 1; } } } int q; cin >> q; while (q--) { int k; cin >> k; cout << ans[k] << endl; } #ifdef HOME cerr << Time << endl; #endif }

Compilation message (stderr)

designated_cities.cpp: In function 'void calc(int, int)':
designated_cities.cpp:25:22: warning: unused variable 'c' [-Wunused-variable]
         int v = e.f, c = e.s;
                      ^
designated_cities.cpp: In function 'void add_out(int, int, long long int)':
designated_cities.cpp:60:22: warning: unused variable 'c' [-Wunused-variable]
         int v = e.f, c = e.s;
                      ^
designated_cities.cpp: In function 'void solve(int)':
designated_cities.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
designated_cities.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
#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...