Submission #102496

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
102496	2019-03-25T11:26:59 Z	Andrei1998	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	1543 ms	67836 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	19072 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	19200 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	19064 KB	Output is correct
2	Correct	1066 ms	65944 KB	Output is correct
3	Correct	712 ms	64632 KB	Output is correct
4	Correct	926 ms	66008 KB	Output is correct
5	Correct	1111 ms	66148 KB	Output is correct
6	Correct	1022 ms	66040 KB	Output is correct
7	Correct	1543 ms	67668 KB	Output is correct
8	Correct	834 ms	65644 KB	Output is correct
9	Correct	1459 ms	67836 KB	Output is correct