oj.uz

Submission #525678

# Submission time Handle Problem Language Result Execution time Memory
525678 2022-02-12T13:50:43 Z Josia Paths (RMI21_paths) C++14
36 / 100
 600 ms 43556 KB 
#include <bits/stdc++.h>

using namespace std;
#define int int64_t



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


void generateParents(int v, int p, int weight) {
    if (parents[v].first != -1) return;

    parents[v].first = p;
    parents[v].second = weight;

    for (auto u: graph[v]) {
        if (parents[u.first].first != -1) continue;
        generateParents(u.first, v, u.second);
    }
    order.push_back(v);
}



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

    vector<int> pointers;

    for (int i = 0; i<n; i++) pointers.push_back(i);

    order.pop_back();

    for (int i: order) {
        int newElem = *prev(tree[pointers[i]].end()) + parents[i].second;
        tree[pointers[i]].erase(*prev(tree[pointers[i]].end()));
        tree[pointers[i]].insert(newElem);

        if (tree[pointers[i]].size() > tree[pointers[parents[i].first]].size()) {
            swap(pointers[i], pointers[parents[i].first]);
        }

        auto it = tree[pointers[i]].begin();

        while (it != tree[pointers[i]].end()) {
            tree[pointers[parents[i].first]].insert(*it);
            it = next(it);
        }
    }



    // cerr << "root element: ";

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


    int res = 0;

    auto it = tree[pointers[v]].end();

    for (int i = 0; i<k; i++) {
        it = prev(it);
        res += *it;
    }

    return res;
}



void solve() {
    
    cin >> n >> k;
    graph.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++) {
        // cerr << i << " ----------------------\n";

        parents.clear();
        parents.assign(n, {-1, 0});
        order.clear();

        generateParents(i, -2, 0);

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

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

        assert(order.back() == i);

        int res = stl(i);

        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 1 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 1 ms 204 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 13 ms 368 KB Output is correct
5 Correct 13 ms 368 KB Output is correct
6 Correct 15 ms 332 KB Output is correct
7 Correct 15 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 1 ms 204 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 13 ms 368 KB Output is correct
5 Correct 13 ms 368 KB Output is correct
6 Correct 15 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 487 ms 900 KB Output is correct
9 Correct 326 ms 624 KB Output is correct
10 Correct 429 ms 692 KB Output is correct
11 Correct 300 ms 600 KB Output is correct
12 Correct 457 ms 768 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 1 ms 204 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 13 ms 368 KB Output is correct
5 Correct 13 ms 368 KB Output is correct
6 Correct 15 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 487 ms 900 KB Output is correct
9 Correct 326 ms 624 KB Output is correct
10 Correct 429 ms 692 KB Output is correct
11 Correct 300 ms 600 KB Output is correct
12 Correct 457 ms 768 KB Output is correct
13 Execution timed out 1018 ms 1164 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 1083 ms 43556 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 1 ms 204 KB Output is correct
3 Correct 15 ms 380 KB Output is correct
4 Correct 13 ms 368 KB Output is correct
5 Correct 13 ms 368 KB Output is correct
6 Correct 15 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 487 ms 900 KB Output is correct
9 Correct 326 ms 624 KB Output is correct
10 Correct 429 ms 692 KB Output is correct
11 Correct 300 ms 600 KB Output is correct
12 Correct 457 ms 768 KB Output is correct
13 Execution timed out 1018 ms 1164 KB Time limit exceeded
14 Halted 0 ms 0 KB -