oj.uz

Submission #794901

# Submission time Handle Problem Language Result Execution time Memory
794901 2023-07-27T02:14:32 Z PurpleCrayon Designated Cities (JOI19_designated_cities) C++17
100 / 100
 962 ms 40912 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;

int n;
vector<ar<int, 3>> adj[N];
ll ans[N];

ll calc_one(int c, int p) {
    ll sum = 0;
    for (auto [nxt, w, _] : adj[c]) if (nxt != p) {
        sum += w + calc_one(nxt, c);
    }
    return sum;
}

void dfs1(int c, int p, ll x) {
    ans[1] = min(ans[1], x);
    for (auto [nxt, a, b] : adj[c]) if (nxt != p) {
        dfs1(nxt, c, x - a + b);
    }
}

int sub[N];
bool blocked[N];

int dfs_sub(int c, int p) {
    sub[c] = 1;
    for (auto [nxt, x, y] : adj[c]) if (nxt != p && !blocked[nxt]) {
        sub[c] += dfs_sub(nxt, c);
    }

    return sub[c];
}

int dfs_cent(int c, int p, int cnt) {
    for (auto [nxt, x, y] : adj[c]) if (nxt != p && !blocked[nxt] && sub[nxt] > cnt / 2)
        return dfs_cent(nxt, c, cnt);

    return c;
}

pair<ll, int> dfs_best(int c, int p, ll x) {
    pair<ll, int> best{x, c};
    for (auto [nxt, w, _] : adj[c]) if (!blocked[nxt] && nxt != p) {
        best = max(best, dfs_best(nxt, c, x + w));
    }

    return best;
}

vector<int> roots;
int process(int c) {
    if (sz(adj[c]) == 1) roots.push_back(c); // can't hurt, and probably useful

    ll best_w = -1;
    int best_nxt = -1, best_c = -1;

    for (auto [nxt, w, _] : adj[c]) if (!blocked[nxt]) {
        auto cur = dfs_best(nxt, c, w);
        if (cur.first > best_w) {
            best_w = cur.first;
            best_nxt = nxt;
            best_c = cur.second;
        }
    }

    if (best_c != -1) {
        roots.push_back(best_c);
    }
    return best_nxt;
}

void build(int c) {
    if (c == -1) return;
    int cnt = dfs_sub(c, -1);
    int cent = dfs_cent(c, -1, cnt);

    int nxt = process(cent);
    blocked[cent] = 1;
    build(nxt);
}


int par[N], par_w[N];
ll sum[N];
bool marked[N];

void dfs_root(int c, int p) {
    par[c] = p;
    for (auto [nxt, w, _] : adj[c]) if (nxt != p) {
        par_w[nxt] = w;
        sum[nxt] = sum[c] + w;
        dfs_root(nxt, c);
    }
}

void add(int root) {
    sum[root] = par_w[root] = 0;
    dfs_root(root, -1);

    auto get_cost = [&](vector<int> p) {
        memset(marked, 0, sizeof(marked));
        vector<ll> cost(n);
        for (int c : p) {
            int cur = c;
            while (cur != -1 && !marked[cur]) {
                marked[cur] = 1;
                cost[c] += par_w[cur];
                cur = par[cur];
            }
        }
        return cost;
    };

    vector<int> p(n); iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int x, int y) {
        return sum[x] > sum[y];
    });
    auto base_cost = get_cost(p);

    sort(p.begin(), p.end(), [&](int x, int y) {
        return base_cost[x] > base_cost[y];
    });
    auto real_cost = get_cost(p);

    ll cur = accumulate(par_w, par_w + n, 0LL);
    sort(real_cost.rbegin(), real_cost.rend());

    int cnt = 1;
    for (ll x : real_cost) {
        cur -= x;
        cnt++;

        ans[cnt] = min(ans[cnt], cur);
    }

    assert(cur == 0);
}

void solve() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        int x, y; cin >> x >> y;
        adj[a].push_back({b, x, y});
        adj[b].push_back({a, y, x});
    }

    fill(ans, ans + n, INF);
    ll cost_one = calc_one(0, -1);
    dfs1(0, -1, cost_one);

    build(0);
    assert(sz(roots) <= 40);
    sort(roots.begin(), roots.end());
    roots.resize(unique(roots.begin(), roots.end()) - roots.begin());
    for (int c : roots) add(c);

    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << ans[x] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5244 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 2 ms 5204 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 2 ms 5204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 447 ms 23676 KB Output is correct
3 Correct 790 ms 34188 KB Output is correct
4 Correct 237 ms 23648 KB Output is correct
5 Correct 217 ms 23468 KB Output is correct
6 Correct 558 ms 25120 KB Output is correct
7 Correct 175 ms 23344 KB Output is correct
8 Correct 669 ms 33900 KB Output is correct
9 Correct 128 ms 23936 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 596 ms 23676 KB Output is correct
3 Correct 728 ms 34204 KB Output is correct
4 Correct 243 ms 23612 KB Output is correct
5 Correct 326 ms 23512 KB Output is correct
6 Correct 656 ms 25684 KB Output is correct
7 Correct 192 ms 23824 KB Output is correct
8 Correct 962 ms 31060 KB Output is correct
9 Correct 132 ms 30096 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5244 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 2 ms 5204 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 2 ms 5204 KB Output is correct
12 Correct 2 ms 5196 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 5 ms 5332 KB Output is correct
16 Correct 6 ms 5412 KB Output is correct
17 Correct 4 ms 5460 KB Output is correct
18 Correct 5 ms 5332 KB Output is correct
19 Correct 4 ms 5332 KB Output is correct
20 Correct 5 ms 5412 KB Output is correct
21 Correct 5 ms 5440 KB Output is correct
22 Correct 4 ms 5332 KB Output is correct
23 Correct 4 ms 5332 KB Output is correct
24 Correct 4 ms 5460 KB Output is correct
25 Correct 5 ms 5460 KB Output is correct
26 Correct 5 ms 5460 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 447 ms 23676 KB Output is correct
3 Correct 790 ms 34188 KB Output is correct
4 Correct 237 ms 23648 KB Output is correct
5 Correct 217 ms 23468 KB Output is correct
6 Correct 558 ms 25120 KB Output is correct
7 Correct 175 ms 23344 KB Output is correct
8 Correct 669 ms 33900 KB Output is correct
9 Correct 128 ms 23936 KB Output is correct
10 Correct 2 ms 5204 KB Output is correct
11 Correct 596 ms 23676 KB Output is correct
12 Correct 728 ms 34204 KB Output is correct
13 Correct 243 ms 23612 KB Output is correct
14 Correct 326 ms 23512 KB Output is correct
15 Correct 656 ms 25684 KB Output is correct
16 Correct 192 ms 23824 KB Output is correct
17 Correct 962 ms 31060 KB Output is correct
18 Correct 132 ms 30096 KB Output is correct
19 Correct 2 ms 5204 KB Output is correct
20 Correct 217 ms 30040 KB Output is correct
21 Correct 772 ms 40628 KB Output is correct
22 Correct 296 ms 28672 KB Output is correct
23 Correct 564 ms 30116 KB Output is correct
24 Correct 239 ms 28908 KB Output is correct
25 Correct 568 ms 30076 KB Output is correct
26 Correct 206 ms 28952 KB Output is correct
27 Correct 308 ms 29932 KB Output is correct
28 Correct 624 ms 31744 KB Output is correct
29 Correct 353 ms 29984 KB Output is correct
30 Correct 263 ms 29116 KB Output is correct
31 Correct 224 ms 29952 KB Output is correct
32 Correct 700 ms 37776 KB Output is correct
33 Correct 132 ms 30428 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5244 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 2 ms 5204 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 2 ms 5204 KB Output is correct
12 Correct 2 ms 5204 KB Output is correct
13 Correct 447 ms 23676 KB Output is correct
14 Correct 790 ms 34188 KB Output is correct
15 Correct 237 ms 23648 KB Output is correct
16 Correct 217 ms 23468 KB Output is correct
17 Correct 558 ms 25120 KB Output is correct
18 Correct 175 ms 23344 KB Output is correct
19 Correct 669 ms 33900 KB Output is correct
20 Correct 128 ms 23936 KB Output is correct
21 Correct 2 ms 5204 KB Output is correct
22 Correct 596 ms 23676 KB Output is correct
23 Correct 728 ms 34204 KB Output is correct
24 Correct 243 ms 23612 KB Output is correct
25 Correct 326 ms 23512 KB Output is correct
26 Correct 656 ms 25684 KB Output is correct
27 Correct 192 ms 23824 KB Output is correct
28 Correct 962 ms 31060 KB Output is correct
29 Correct 132 ms 30096 KB Output is correct
30 Correct 2 ms 5196 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 5 ms 5460 KB Output is correct
33 Correct 5 ms 5332 KB Output is correct
34 Correct 6 ms 5412 KB Output is correct
35 Correct 4 ms 5460 KB Output is correct
36 Correct 5 ms 5332 KB Output is correct
37 Correct 4 ms 5332 KB Output is correct
38 Correct 5 ms 5412 KB Output is correct
39 Correct 5 ms 5440 KB Output is correct
40 Correct 4 ms 5332 KB Output is correct
41 Correct 4 ms 5332 KB Output is correct
42 Correct 4 ms 5460 KB Output is correct
43 Correct 5 ms 5460 KB Output is correct
44 Correct 5 ms 5460 KB Output is correct
45 Correct 2 ms 5204 KB Output is correct
46 Correct 217 ms 30040 KB Output is correct
47 Correct 772 ms 40628 KB Output is correct
48 Correct 296 ms 28672 KB Output is correct
49 Correct 564 ms 30116 KB Output is correct
50 Correct 239 ms 28908 KB Output is correct
51 Correct 568 ms 30076 KB Output is correct
52 Correct 206 ms 28952 KB Output is correct
53 Correct 308 ms 29932 KB Output is correct
54 Correct 624 ms 31744 KB Output is correct
55 Correct 353 ms 29984 KB Output is correct
56 Correct 263 ms 29116 KB Output is correct
57 Correct 224 ms 29952 KB Output is correct
58 Correct 700 ms 37776 KB Output is correct
59 Correct 132 ms 30428 KB Output is correct
60 Correct 2 ms 5204 KB Output is correct
61 Correct 541 ms 30344 KB Output is correct
62 Correct 666 ms 40912 KB Output is correct
63 Correct 282 ms 28872 KB Output is correct
64 Correct 356 ms 30368 KB Output is correct
65 Correct 231 ms 29088 KB Output is correct
66 Correct 374 ms 30328 KB Output is correct
67 Correct 213 ms 29116 KB Output is correct
68 Correct 292 ms 30180 KB Output is correct
69 Correct 700 ms 31928 KB Output is correct
70 Correct 353 ms 30192 KB Output is correct
71 Correct 254 ms 29300 KB Output is correct
72 Correct 186 ms 30120 KB Output is correct
73 Correct 785 ms 37936 KB Output is correct
74 Correct 165 ms 31500 KB Output is correct