oj.uz

Submission #525943

# Submission time Handle Problem Language Result Execution time Memory
525943 2022-02-13T09:26:38 Z Josia Paths (RMI21_paths) C++14
36 / 100
 600 ms 11168 KB 
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;
#define int int64_t



vector<int> parents;
vector<vector<pair<int, int>>> graph;
int n, k;



void merge(priority_queue<int> &A, priority_queue<int> &B) {
    if (A.size() > B.size()) A.swap(B);
    while(A.size()) {B.push(A.top()); A.pop();}
}



priority_queue<int> dfs(int v, int p) {
    priority_queue<int> res;

    res.push(0);

    if (parents[v] != -1) return res;

    parents[v] = p;

    for (auto u: graph[v]) {
        if (parents[u.first] != -1) continue;
        priority_queue<int> tmp = dfs(u.first, v);

        int newElem = tmp.top() + u.second;
        tmp.pop();
        tmp.push(newElem);

        merge(tmp, res);
    }

    return res;
}



// int stl(int v) {
//     vector<priority_queue<int>> tree(n);  // offset, options

//     for (int i = 0; i<n; i++) {
//         if (graph[i].size() == 1 && i!=v) tree[i].push(0);
//     }

//     order.pop_back();

//     for (int i: order) {
//         int newElem = tree[i].top() + parents[i].second;
//         tree[i].pop();
//         tree[i].push(newElem);

//         merge(tree[i], tree[parents[i].first]);
//     }

//     // cerr << "root element: ";

//     // for (int i: tree[v]) {
//     //     cerr << i << " ";
//     // } cerr << "\n";


//     int res = 0;

//     for (int i = 0; i<k; i++) {
//         res += tree[v].top();
//         tree[v].pop();
//     }

//     return res;
// }



void solve() {
    
    cin >> n >> k;
    graph.resize(n);
    parents.resize(n);

    for (int i = 0; i<n-1; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    for (int i = 0; i<n; i++) {
        // parents.clear();
        fill(parents.begin(), parents.end(), -1);

        priority_queue<int> pq = dfs(i, -2);

        // cerr << "order: ";
        // for (auto i: order) {
        //     cerr << i << " ";
        // } cerr << "\n";

        // cerr << "parents: ";
        // for (auto i: parents) {
        //     cerr << i.first << " ";
        // } cerr << "\n";

        int res = 0;

        for (int i = 0; i<k; i++) {
            res += pq.top();
            pq.pop();
        }

        cout << res << "\n";
        // cerr << "result: " << res << "\n";
    }
    


}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    solve();

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 137 ms 420 KB Output is correct
9 Correct 132 ms 504 KB Output is correct
10 Correct 114 ms 452 KB Output is correct
11 Correct 80 ms 416 KB Output is correct
12 Correct 121 ms 432 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 137 ms 420 KB Output is correct
9 Correct 132 ms 504 KB Output is correct
10 Correct 114 ms 452 KB Output is correct
11 Correct 80 ms 416 KB Output is correct
12 Correct 121 ms 432 KB Output is correct
13 Execution timed out 688 ms 532 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 11168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 137 ms 420 KB Output is correct
9 Correct 132 ms 504 KB Output is correct
10 Correct 114 ms 452 KB Output is correct
11 Correct 80 ms 416 KB Output is correct
12 Correct 121 ms 432 KB Output is correct
13 Execution timed out 688 ms 532 KB Time limit exceeded
14 Halted 0 ms 0 KB -