oj.uz

Submission #1109682

# Submission time Handle Problem Language Result Execution time Memory
1109682 2024-11-07T10:05:46 Z _callmelucian Designated Cities (JOI19_designated_cities) C++14
39 / 100
 2000 ms 61740 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;

struct IT {
    vector<pl> tr;
    vector<ll> lazy;

    IT (int sz) : tr(4 * sz), lazy(4 * sz) {}

    void apply (int k, ll val) {
        tr[k].first += val, lazy[k] += val;
    }

    void pushDown (int k) {
        if (lazy[k])
            apply(2 * k, lazy[k]), apply(2 * k + 1, lazy[k]), lazy[k] = 0;
    }

    void build (int k, int l, int r, vector<pl> &a) {
        if (l == r)
            return tr[k] = a[l], void();
        int mid = (l + r) >> 1;
        build(2 * k, l, mid, a);
        build(2 * k + 1, mid + 1, r, a);
        tr[k] = max(tr[2 * k], tr[2 * k + 1]);
    }

    void update (int a, int b, ll val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (l == r)
            return apply(k, val), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, val, 2 * k, l, mid);
        update(a, b, val, 2 * k + 1, mid + 1, r);
        tr[k] = max(tr[2 * k], tr[2 * k + 1]);
    }

    pl getBest() { return tr[1]; }
};

vector<tpl> adj[mn];
ll ans[mn], n;

namespace originalTree {
    int bestLeaf[mn], secLeaf[mn];
    ll downPath[mn], upPath[mn], sumDown;

    void dfs (int u, int p, ll pA, ll pH) {
        // construct costs on paths
        downPath[u] = downPath[p] + pA;
        upPath[u] = upPath[p] + pH;
        bestLeaf[u] = u;

        // run dfs down
        for (tpl item : adj[u]) {
            int v, away, home; tie(v, away, home) = item;
            if (v == p) continue;
            dfs(v, u, away, home);

            sumDown += away;
            if (downPath[bestLeaf[v]] > downPath[bestLeaf[u]])
                secLeaf[u] = bestLeaf[u], bestLeaf[u] = bestLeaf[v];
            else if (downPath[bestLeaf[v]] > downPath[secLeaf[u]]) secLeaf[u] = bestLeaf[v];
        }
    }

    ll tryNode (int u) {
        ll pathOne = downPath[bestLeaf[u]] - (bestLeaf[u] ? downPath[u] : 0);
        ll pathTwo = downPath[secLeaf[u]] - (secLeaf[u] ? downPath[u] : 0);
        return sumDown - pathOne - pathTwo - downPath[u] + upPath[u];
    }

    ll chooseNode (int u) {
        return sumDown - downPath[u] + upPath[u];
    }
}

namespace modifiedTree {
    int num[mn], sz[mn], up[mn], toP[mn], timeDfs;
    bool colored[mn];
    ll weight[mn];
    IT tree(mn);

    bool dfs (int u, int p, int y, int w) {
        num[u] = ++timeDfs, sz[u] = 1, up[u] = p, toP[u] = w;
        if (u == y) colored[u] = 1;

        for (tpl item : adj[u]) {
            int v, away, home; tie(v, away, home) = item;
            if (v == p) continue;
            if (dfs(v, u, y, away)) colored[u] = 1;
            sz[u] += sz[v];
        }
        return colored[u];
    }

    void buildTree() {
        vector<pl> a(n + 1);
        for (int i = 1; i <= n; i++)
            a[num[i]] = make_pair(0, i);
        for (int i = 1; i <= n; i++) {
            int u = a[i].second;
            if (!colored[u])
                a[i].first = weight[u] = weight[up[u]] + toP[u];
        }
        tree.build(1, 1, n, a);
    }

    void colorNode (int u) {
        while (!colored[u]) {
            tree.update(num[u], num[u] + sz[u] - 1, -toP[u], 1, 1, n);
            colored[u] = 1, u = up[u];
        }
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        adj[a].emplace_back(b, c, d);
        adj[b].emplace_back(a, d, c);
    }
    originalTree::dfs(1, 1, 0, 0);

    for (int i = 1; i <= n; i++) ans[i] = LLONG_MAX;

    int optX = 0, optY = 0;
    for (int i = 1; i <= n; i++) {
        ll cur = originalTree::tryNode(i);
        if (cur < ans[2])
            ans[2] = cur, optX = originalTree::bestLeaf[i], optY = originalTree::secLeaf[i];

        ans[1] = min(ans[1], originalTree::chooseNode(i));
    }
    modifiedTree::dfs(optX, optX, optY, 0);
    modifiedTree::buildTree();

    for (int i = 3; i <= n; i++) {
        ll delta; int node; tie(delta, node) = modifiedTree::tree.getBest();
        ans[i] = ans[i - 1] - delta;
        modifiedTree::colorNode(node);
    }

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

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28752 KB Output is correct
2 Correct 282 ms 46232 KB Output is correct
3 Correct 134 ms 58440 KB Output is correct
4 Correct 566 ms 46248 KB Output is correct
5 Correct 205 ms 46264 KB Output is correct
6 Correct 186 ms 48200 KB Output is correct
7 Correct 222 ms 46076 KB Output is correct
8 Correct 193 ms 59508 KB Output is correct
9 Correct 193 ms 49896 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28920 KB Output is correct
2 Correct 329 ms 46460 KB Output is correct
3 Correct 207 ms 61740 KB Output is correct
4 Correct 531 ms 49004 KB Output is correct
5 Correct 193 ms 46080 KB Output is correct
6 Correct 210 ms 48744 KB Output is correct
7 Correct 182 ms 46324 KB Output is correct
8 Correct 171 ms 55632 KB Output is correct
9 Correct 164 ms 46252 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28752 KB Output is correct
2 Correct 5 ms 28752 KB Output is correct
3 Correct 5 ms 28752 KB Output is correct
4 Correct 7 ms 28796 KB Output is correct
5 Correct 5 ms 28752 KB Output is correct
6 Correct 6 ms 28652 KB Output is correct
7 Correct 6 ms 28752 KB Output is correct
8 Correct 5 ms 28752 KB Output is correct
9 Correct 5 ms 28920 KB Output is correct
10 Correct 5 ms 28752 KB Output is correct
11 Correct 5 ms 28752 KB Output is correct
12 Correct 6 ms 28752 KB Output is correct
13 Correct 7 ms 28752 KB Output is correct
14 Correct 7 ms 29008 KB Output is correct
15 Correct 7 ms 28752 KB Output is correct
16 Correct 7 ms 29008 KB Output is correct
17 Correct 7 ms 28792 KB Output is correct
18 Correct 6 ms 29008 KB Output is correct
19 Correct 7 ms 29024 KB Output is correct
20 Correct 6 ms 28752 KB Output is correct
21 Correct 8 ms 29176 KB Output is correct
22 Correct 9 ms 28912 KB Output is correct
23 Correct 7 ms 28752 KB Output is correct
24 Correct 7 ms 29008 KB Output is correct
25 Correct 7 ms 29008 KB Output is correct
26 Correct 7 ms 29024 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28752 KB Output is correct
2 Correct 282 ms 46232 KB Output is correct
3 Correct 134 ms 58440 KB Output is correct
4 Correct 566 ms 46248 KB Output is correct
5 Correct 205 ms 46264 KB Output is correct
6 Correct 186 ms 48200 KB Output is correct
7 Correct 222 ms 46076 KB Output is correct
8 Correct 193 ms 59508 KB Output is correct
9 Correct 193 ms 49896 KB Output is correct
10 Correct 6 ms 28920 KB Output is correct
11 Correct 329 ms 46460 KB Output is correct
12 Correct 207 ms 61740 KB Output is correct
13 Correct 531 ms 49004 KB Output is correct
14 Correct 193 ms 46080 KB Output is correct
15 Correct 210 ms 48744 KB Output is correct
16 Correct 182 ms 46324 KB Output is correct
17 Correct 171 ms 55632 KB Output is correct
18 Correct 164 ms 46252 KB Output is correct
19 Correct 6 ms 28920 KB Output is correct
20 Correct 398 ms 46392 KB Output is correct
21 Correct 177 ms 58388 KB Output is correct
22 Correct 592 ms 46152 KB Output is correct
23 Correct 327 ms 46484 KB Output is correct
24 Correct 573 ms 49112 KB Output is correct
25 Correct 351 ms 49676 KB Output is correct
26 Correct 704 ms 48968 KB Output is correct
27 Correct 224 ms 46212 KB Output is correct
28 Correct 199 ms 51840 KB Output is correct
29 Execution timed out 2064 ms 46680 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28752 KB Output is correct
2 Correct 5 ms 28752 KB Output is correct
3 Correct 5 ms 28752 KB Output is correct
4 Correct 7 ms 28796 KB Output is correct
5 Correct 5 ms 28752 KB Output is correct
6 Correct 6 ms 28652 KB Output is correct
7 Correct 6 ms 28752 KB Output is correct
8 Correct 5 ms 28752 KB Output is correct
9 Correct 5 ms 28920 KB Output is correct
10 Correct 5 ms 28752 KB Output is correct
11 Correct 5 ms 28752 KB Output is correct
12 Correct 5 ms 28752 KB Output is correct
13 Correct 282 ms 46232 KB Output is correct
14 Correct 134 ms 58440 KB Output is correct
15 Correct 566 ms 46248 KB Output is correct
16 Correct 205 ms 46264 KB Output is correct
17 Correct 186 ms 48200 KB Output is correct
18 Correct 222 ms 46076 KB Output is correct
19 Correct 193 ms 59508 KB Output is correct
20 Correct 193 ms 49896 KB Output is correct
21 Correct 6 ms 28920 KB Output is correct
22 Correct 329 ms 46460 KB Output is correct
23 Correct 207 ms 61740 KB Output is correct
24 Correct 531 ms 49004 KB Output is correct
25 Correct 193 ms 46080 KB Output is correct
26 Correct 210 ms 48744 KB Output is correct
27 Correct 182 ms 46324 KB Output is correct
28 Correct 171 ms 55632 KB Output is correct
29 Correct 164 ms 46252 KB Output is correct
30 Correct 6 ms 28752 KB Output is correct
31 Correct 7 ms 28752 KB Output is correct
32 Correct 7 ms 29008 KB Output is correct
33 Correct 7 ms 28752 KB Output is correct
34 Correct 7 ms 29008 KB Output is correct
35 Correct 7 ms 28792 KB Output is correct
36 Correct 6 ms 29008 KB Output is correct
37 Correct 7 ms 29024 KB Output is correct
38 Correct 6 ms 28752 KB Output is correct
39 Correct 8 ms 29176 KB Output is correct
40 Correct 9 ms 28912 KB Output is correct
41 Correct 7 ms 28752 KB Output is correct
42 Correct 7 ms 29008 KB Output is correct
43 Correct 7 ms 29008 KB Output is correct
44 Correct 7 ms 29024 KB Output is correct
45 Correct 6 ms 28920 KB Output is correct
46 Correct 398 ms 46392 KB Output is correct
47 Correct 177 ms 58388 KB Output is correct
48 Correct 592 ms 46152 KB Output is correct
49 Correct 327 ms 46484 KB Output is correct
50 Correct 573 ms 49112 KB Output is correct
51 Correct 351 ms 49676 KB Output is correct
52 Correct 704 ms 48968 KB Output is correct
53 Correct 224 ms 46212 KB Output is correct
54 Correct 199 ms 51840 KB Output is correct
55 Execution timed out 2064 ms 46680 KB Time limit exceeded
56 Halted 0 ms 0 KB -