oj.uz

Submission #716525

# Submission time Handle Problem Language Result Execution time Memory
716525 2023-03-30T08:56:52 Z Stickfish Paths (RMI21_paths) C++17
56 / 100
 406 ms 37200 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 123;
vector<pair<int, int>> edg[MAXN];
ll cost[MAXN * 2];
pair<int, int> edges[MAXN * 3];
vector<ll> dp[MAXN * 2];

void get_dp(int e, int k) {
    if (dp[e].size())
        return;
    auto [rt, v] = edges[e];
    for (auto [u, ne] : edg[v]) {
        if (u == rt)
            continue;
        get_dp(ne, k);
        vector<ll> ndp(dp[e].size() + dp[ne].size());
        merge(dp[e].rbegin(), dp[e].rend(), dp[ne].rbegin(), dp[ne].rend(), ndp.rbegin());
        ndp.resize(min(int(ndp.size()), k));
        dp[e] = ndp;
    }
    if (dp[e].empty()) {
        dp[e] = {cost[e]};
    } else {
        dp[e][0] += cost[e];
    }
}

signed main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i + 1 < n; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        edg[u].push_back({v, i * 2});
        edg[v].push_back({u, i * 2 + 1});
        edges[i * 2] = {u, v};
        edges[i * 2 + 1] = {v, u};
        cost[i * 2] = cost[i * 2 + 1] = c;
    }
    for (int e = 2 * n; e < 3 * n; ++e) {
        edges[e] = {n, e - 2 * n};
        get_dp(e, k);
        ll ans = 0;
        for (auto x : dp[e])
            ans += x;
        cout << ans << '\n';
    }
    //for (int e = 0; e < n * 2 - 1; ++e)
        //get_dp(e, k);
    //for (int v = 0; v < n; ++v) {
        //vector<ll> ans;
        //for (auto [u, e] : edg[v]) {
            //vector<ll> ndp(ans.size() + dp[e].size());
            //merge(dp[e].rbegin(), dp[e].rend(), ans.rbegin(), ans.rend(), ndp.rbegin());
            //ndp.resize(min(int(ndp.size()), k));
            //ans = ndp;
        //}
        //ll anssm = 0;
        //for (auto x : ans)
            //anssm += x;
        //cout << anssm << '\n';
    //}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7292 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7292 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 6 ms 7380 KB Output is correct
6 Correct 5 ms 7444 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 7 ms 9044 KB Output is correct
9 Correct 7 ms 8404 KB Output is correct
10 Correct 6 ms 8020 KB Output is correct
11 Correct 41 ms 9008 KB Output is correct
12 Correct 6 ms 8660 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7292 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 6 ms 7380 KB Output is correct
6 Correct 5 ms 7444 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 7 ms 9044 KB Output is correct
9 Correct 7 ms 8404 KB Output is correct
10 Correct 6 ms 8020 KB Output is correct
11 Correct 41 ms 9008 KB Output is correct
12 Correct 6 ms 8660 KB Output is correct
13 Correct 29 ms 27176 KB Output is correct
14 Correct 13 ms 12628 KB Output is correct
15 Correct 8 ms 8532 KB Output is correct
16 Correct 406 ms 22916 KB Output is correct
17 Correct 14 ms 17084 KB Output is correct
18 Correct 12 ms 11988 KB Output is correct
19 Correct 29 ms 32188 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 37200 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7292 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 6 ms 7380 KB Output is correct
6 Correct 5 ms 7444 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 7 ms 9044 KB Output is correct
9 Correct 7 ms 8404 KB Output is correct
10 Correct 6 ms 8020 KB Output is correct
11 Correct 41 ms 9008 KB Output is correct
12 Correct 6 ms 8660 KB Output is correct
13 Correct 29 ms 27176 KB Output is correct
14 Correct 13 ms 12628 KB Output is correct
15 Correct 8 ms 8532 KB Output is correct
16 Correct 406 ms 22916 KB Output is correct
17 Correct 14 ms 17084 KB Output is correct
18 Correct 12 ms 11988 KB Output is correct
19 Correct 29 ms 32188 KB Output is correct
20 Runtime error 172 ms 37200 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -