oj.uz

Submission #102495

# Submission time Handle Problem Language Result Execution time Memory
102495 2019-03-25T11:25:50 Z Andrei1998 Designated Cities (JOI19_designated_cities) C++17
0 / 100
 1062 ms 66092 KB 
#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, 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 20 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 21 ms 19072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19072 KB Output is correct
2 Incorrect 1062 ms 66092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

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