Submission #102497

#	Time	Username	Problem	Language	Result	Execution time	Memory
102497		Andrei1998	Designated Cities (JOI19_designated_cities)	C++17	56 / 100	2025 ms	100956 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

typedef long long int lint;

const int NMAX = 200000 + 5;

int N;
set <int> tree[NMAX];
inline int parent(int node) { return *tree[node].begin(); }
map <lint, int> cost[NMAX];

lint ans[NMAX];

int main() {
    cin >> N;
    for (int i = 1; i < N; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        tree[a].insert(b);
        tree[b].insert(a);
        cost[a][b] = c;
        cost[b][a] = d;
    }

    // E = 1
    lint sum = 0;
    function <void(int, int)> dfs_compute_from_1 = [&sum, &dfs_compute_from_1](const int node, const int father) {
        for (auto it: tree[node]) {
            if (it != father) {
                sum += cost[node][it];
                dfs_compute_from_1(it, node);
            }
        }
    };

    function <void(int, int)> dfs_compute = [&sum, &dfs_compute](const int node, const int father) {
        ans[1] = min(ans[1], sum);
        for (auto it: tree[node]) {
            if (it != father) {
                sum += cost[it][node] - cost[node][it];
                dfs_compute(it, node);
                sum -= cost[it][node] - cost[node][it];
            }
        }
    };
    dfs_compute_from_1(1, 0);
    ans[1] = sum;
    dfs_compute(1, 0);

    // E > 1
    priority_queue <pair <lint, int> > pq;
    for (int i = 1; i <= N; ++i) {
        if (tree[i].size() == 1) {
            pq.emplace(-cost[parent(i)][i], i);
        }
    }

    for (int i = pq.size(); i <= N; ++i) {
        ans[i] = 0;
    }

    int where = pq.size() - 1;
    while (where > 1) {
        int node; lint cst;
        tie(cst, node) = pq.top();
        cst = -cst;
        pq.pop();

        const int father = parent(node);
        tree[father].erase(node);
        if (tree[father].size() == 1) {
            pq.emplace(-(cst + cost[parent(father)][father]), father);
        } else {
            ans[where] = ans[where + 1] + cst;
            --where;
        }
    }

    int Q = 0;
    cin >> Q;
    for (int i = 1; i <= Q; ++i) {
        int E;
        cin >> E;
        cout << ans[E] << '\n';
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 0 / 44