Submission #223986

#TimeUsernameProblemLanguageResultExecution timeMemory
223986osaaateiasavtnlDesignated Cities (JOI19_designated_cities)C++14
100 / 100
529 ms59112 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 N = 2e5 + 7; const ll INF = 1e18; int n; vector <ii> g[N]; 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) { 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]; vector <pair <ll, int> > a; void solve(int c) { build(c, c); ll sum = 0; ladder(c, 0, sum); a.clear(); print(c, c, 0, a, 1); sort(all(a)); reverse(all(a)); ans[1] = min(ans[1], 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], sum); } else { ans[i + 1] = min(ans[i + 1], sum + a[i].f - a[l].f); } } } namespace Root { ll sum[N]; void dfs1(int u, int p) { for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p) { dfs1(v, u); sum[u] += sum[v] + c; } } } ll diam = INF; int root = 1; pair <ll, int> h[N]; void dfs2(int u, int p, ll up) { for (auto e : g[u]) { int v = e.f, c = e.s; if (v == p) { up += c; } } ans[1] = min(ans[1], up + sum[u]); h[u] = mp(0, u); for (auto e : g[u]) { int v = e.f, c = e.s; if (v != p) { dfs2(v, u, up + sum[u] - sum[v] - c); auto t = h[v]; t.f += c; ll nn = up + sum[u] - h[u].f - t.f; if (nn < diam) { diam = nn; root = t.s; } h[u] = max(h[u], t); } } } int getroot() { dfs1(1, 1); dfs2(1, 1, 0); return root; } }; 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)); } for (int i = 0; i < N; ++i) ans[i] = INF; int root = Root::getroot(); solve(root); #ifdef HOME cout << "root " << root << endl; #endif 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 solve(int)':
designated_cities.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
designated_cities.cpp:82: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...