Submission #102496

#	Time	Username	Problem	Language	Result	Execution time	Memory
102496		Andrei1998	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	1543 ms	67836 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() {
    //freopen("data.in", "r", stdin);

    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;
    }

    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;
        }
    }

    /*for (int i = 1; i <= N; ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;*/

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

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