oj.uz

Submission #645586

# Submission time Handle Problem Language Result Execution time Memory
645586 2022-09-27T11:29:54 Z Vanilla Paths (RMI21_paths) C++17
68 / 100
 484 ms 27108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair <int64, int64> pii;
const int maxn = 2e3 + 2;
vector <pii> ad [maxn];
vector <pii> lv;
priority_queue <int64> rs [maxn];
int dad [maxn];
int leaves = 0;
const int64 maxn1 = 1e5 + 2;
vector <int> ad1 [maxn1];
map <pair <int, int>, int64> cost1;
int64 dp [maxn1];
void dfs1 (int u, int p) {
    // cerr << u << " ";
    for (int v: ad1[u]) {
        if (v == p) continue;
        dfs1(v, u);
        dp[u] = max(dp[u], dp[v] + cost1[{u, v}]);
    }
}

void dfs2 (int u, int p, int64 sf) {
    dp[u] = max(dp[u], sf);
    vector <int> nd;
    for (int v: ad1[u]) {
        if (v == p) continue;
        nd.push_back(v);
    }
    int m = nd.size();
    vector <int64> pref(m), suff(m);
    if (m) {
        pref[0] = dp[nd[0]] + cost1[{u, nd[0]}];
        suff[m-1] = dp[nd[m-1]] + cost1[{u, nd[m-1]}];
        for (int i = 1; i < m; i++){
            pref[i] = max(pref[i-1], dp[nd[i]] + cost1[{u, nd[i]}]);
        }
        for (int i = m - 2; i >= 0; i--){
            suff[i] = max(suff[i + 1], dp[nd[i]] + cost1[{u, nd[i]}]);
        }
        for (int i = 0; i < m; i++){
            int64 p1 = (i ? pref[i-1]: 0);
            int64 p2 = ((i != m - 1) ? suff[i + 1]: 0);
            // cout << u << " " << nd[i] << " " << p1 << " " << p2 << " " << sf << " " << "\n";
            dfs2(nd[i], u, max({p1, p2, sf}) + cost1[{u, nd[i]}]);
        }
    }
}

void dfs (int u, int p) {
    while (!rs[u].empty()) rs[u].pop();
    for (auto [v, c]: ad[u]) {
        if (v == p) continue;
        dfs(v, u);
        int64 k = rs[v].top(); rs[v].pop();
        rs[v].push(k + c);
        if (rs[u].size() < rs[v].size()) swap(rs[u], rs[v]);
        while (!rs[v].empty()) {
            rs[u].push(rs[v].top());
            rs[v].pop();
        }
    }
    if (rs[u].empty()) rs[u].push(0);
    // cout << "> " << u << " " << rs[u].top() << "\n";
}

int main() {
    int n,k;
    cin >> n >> k;
    if (k == 1) {
        for (int i = 0; i < n - 1; i++){
            int a,b,c;
            cin >> a >> b >> c;
            ad1[a].push_back(b);
            ad1[b].push_back(a);
            cost1[{a,b}] = cost1[{b, a}] = c;
        }
        dfs1(1, -1);
        dfs2(1, -1, 0);
        for (int i = 1; i <= n; i++){
            // cout << i << ": ";
            cout << dp[i] << "\n";
        }
    }
    else {
        for (int i = 0; i < n - 1; i++){
            int a,b,c;
            cin >> a >> b >> c;
            ad[a].push_back({b, c});
            ad[b].push_back({a, c});
        }
        for (int i = 1; i <= n; i++){
            dfs(i, -1);
            int64 frs = 0;
            for (int j = 0; j < k && rs[i].size(); j++) {
                frs+=rs[i].top();
                rs[i].pop();
            }
            cout << frs << "\n";
        }
            
        
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 6 ms 2900 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 6 ms 2900 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 95 ms 5788 KB Output is correct
9 Correct 88 ms 5812 KB Output is correct
10 Correct 40 ms 3544 KB Output is correct
11 Correct 76 ms 8924 KB Output is correct
12 Correct 51 ms 4292 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 6 ms 2900 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 95 ms 5788 KB Output is correct
9 Correct 88 ms 5812 KB Output is correct
10 Correct 40 ms 3544 KB Output is correct
11 Correct 76 ms 8924 KB Output is correct
12 Correct 51 ms 4292 KB Output is correct
13 Correct 484 ms 20312 KB Output is correct
14 Correct 382 ms 14872 KB Output is correct
15 Correct 156 ms 4496 KB Output is correct
16 Correct 328 ms 24200 KB Output is correct
17 Correct 258 ms 8984 KB Output is correct
18 Correct 217 ms 11984 KB Output is correct
19 Correct 458 ms 14584 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 21160 KB Output is correct
2 Correct 365 ms 27108 KB Output is correct
3 Correct 261 ms 21152 KB Output is correct
4 Correct 396 ms 21336 KB Output is correct
5 Correct 319 ms 23208 KB Output is correct
6 Correct 338 ms 21340 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 6 ms 2900 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 95 ms 5788 KB Output is correct
9 Correct 88 ms 5812 KB Output is correct
10 Correct 40 ms 3544 KB Output is correct
11 Correct 76 ms 8924 KB Output is correct
12 Correct 51 ms 4292 KB Output is correct
13 Correct 484 ms 20312 KB Output is correct
14 Correct 382 ms 14872 KB Output is correct
15 Correct 156 ms 4496 KB Output is correct
16 Correct 328 ms 24200 KB Output is correct
17 Correct 258 ms 8984 KB Output is correct
18 Correct 217 ms 11984 KB Output is correct
19 Correct 458 ms 14584 KB Output is correct
20 Correct 316 ms 21160 KB Output is correct
21 Correct 365 ms 27108 KB Output is correct
22 Correct 261 ms 21152 KB Output is correct
23 Correct 396 ms 21336 KB Output is correct
24 Correct 319 ms 23208 KB Output is correct
25 Correct 338 ms 21340 KB Output is correct
26 Runtime error 5 ms 5460 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -