oj.uz

Submission #645532

# Submission time Handle Problem Language Result Execution time Memory
645532 2022-09-27T09:59:00 Z Vanilla Paths (RMI21_paths) C++17
31 / 100
 600 ms 28448 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair <int64, int64> pii;
const int maxn = 1e3 + 2;
vector <int> ad [maxn];
vector <pii> lv;
int64 cost [maxn][maxn];
int dad [maxn];
int leaves = 0;
const int64 maxn1 = 1e5 + 2;
vector <int> ad1 [maxn];
map <pair <int, int>, int64> cost1;
int64 dp [maxn1];

void prec (int u, int p, int64 sum) {
    bool f = 0;
    for (int v: ad[u]) {
        if (v == p) continue;
        f = 1;
        dad[v] = u;
        prec(v, u, sum + cost[u][v]);
    }
    if (!f) lv.push_back({sum, u});
}

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]}]);
        }
    }
}

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;
            cost[a][b] = cost[b][a] = c;
            ad[a].push_back(b);
            ad[b].push_back(a);
        }
        for (int i = 1; i <= n; i++){
            if (ad[i].size() == 1) leaves++;
        }
        if (ad[1].size() == 1) leaves--;
        for (int i = 1; i <= n; i++){
            // k = min(k, leaves);
            int64 rs = 0;
            vector <pair <pii, int> > back;
            for (int j = 0; j < k; j++){
                lv.clear();
                prec(i, -1, 0);
                dad[i] = -1;
                sort(lv.rbegin(), lv.rend());
                // cout << i << " " << j << " " << lv[0].first << " " << lv[0].second << "\n";
                rs+=lv[0].first;
                int k = lv[0].second;
                while (k != i) {
                    int p = dad[k];
                    if (cost[p][k]) back.push_back({{p, k}, cost[p][k]});
                    cost[p][k] = 0;
                    k = p;
                }
            }
            for (auto [x, y]: back) {
                cost[x.first][x.second] = y;
            }
            // cout << i << ": ";
            cout << rs << "\n";
            
        }
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 1212 KB Output is correct
4 Correct 16 ms 1260 KB Output is correct
5 Correct 26 ms 1228 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 15 ms 1260 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 1212 KB Output is correct
4 Correct 16 ms 1260 KB Output is correct
5 Correct 26 ms 1228 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 15 ms 1260 KB Output is correct
8 Execution timed out 1082 ms 5588 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 1212 KB Output is correct
4 Correct 16 ms 1260 KB Output is correct
5 Correct 26 ms 1228 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 15 ms 1260 KB Output is correct
8 Execution timed out 1082 ms 5588 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 20300 KB Output is correct
2 Correct 316 ms 28448 KB Output is correct
3 Correct 235 ms 22492 KB Output is correct
4 Correct 300 ms 22504 KB Output is correct
5 Correct 341 ms 24564 KB Output is correct
6 Correct 312 ms 22632 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 23 ms 1212 KB Output is correct
4 Correct 16 ms 1260 KB Output is correct
5 Correct 26 ms 1228 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 15 ms 1260 KB Output is correct
8 Execution timed out 1082 ms 5588 KB Time limit exceeded
9 Halted 0 ms 0 KB -