oj.uz

Submission #537591

# Submission time Handle Problem Language Result Execution time Memory
537591 2022-03-15T09:25:06 Z joelau Paths (RMI21_paths) C++14
36 / 100
 287 ms 15768 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K, dp[1005][105], num[1005], tmp[105];
vector< pair<long long,long long> > lst[100005];

void dfs (long long x, long long p) {
    memset(dp[x],-1,sizeof(dp[x]));
    num[x] = 0, dp[x][0] = 0;
    for (auto v: lst[x]) if (v.first != p) {
        dfs(v.first,x);
        num[x] += num[v.first];
    }
    if (num[x] == 0) num[x] = 1, dp[x][1] = 0;
    for (auto v: lst[x]) if (v.first != p) {
        for (long long i = 0; i <= num[x] && i <= K; ++i) tmp[i] = dp[x][i];
        for (long long i = 1; i <= num[v.first] && i <= K && dp[v.first][i] != -1; ++i)
            for (long long j = 0; i+j <= num[x] && dp[x][j] != -1 && i+j <= K; ++j)
                tmp[i+j] = max(tmp[i+j],dp[v.first][i] + dp[x][j] + v.second);
        swap(tmp,dp[x]);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    for (long long i = 0; i < N-1; ++i) {
        long long u,v,w; cin >> u >> v >> w; u--, v--;
        lst[u].emplace_back(v,w), lst[v].emplace_back(u,w);
    }
    for (long long i = 0; i < N; ++i) {
        dfs(i,-1);
        cout << dp[i][K] << '\n';
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 11 ms 2856 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 10 ms 2860 KB Output is correct
6 Correct 9 ms 2772 KB Output is correct
7 Correct 10 ms 2860 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 11 ms 2856 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 10 ms 2860 KB Output is correct
6 Correct 9 ms 2772 KB Output is correct
7 Correct 10 ms 2860 KB Output is correct
8 Correct 282 ms 3564 KB Output is correct
9 Correct 287 ms 3748 KB Output is correct
10 Correct 250 ms 3580 KB Output is correct
11 Correct 279 ms 3552 KB Output is correct
12 Correct 240 ms 3544 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 11 ms 2856 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 10 ms 2860 KB Output is correct
6 Correct 9 ms 2772 KB Output is correct
7 Correct 10 ms 2860 KB Output is correct
8 Correct 282 ms 3564 KB Output is correct
9 Correct 287 ms 3748 KB Output is correct
10 Correct 250 ms 3580 KB Output is correct
11 Correct 279 ms 3552 KB Output is correct
12 Correct 240 ms 3544 KB Output is correct
13 Runtime error 5 ms 5424 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 15768 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 11 ms 2856 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 10 ms 2860 KB Output is correct
6 Correct 9 ms 2772 KB Output is correct
7 Correct 10 ms 2860 KB Output is correct
8 Correct 282 ms 3564 KB Output is correct
9 Correct 287 ms 3748 KB Output is correct
10 Correct 250 ms 3580 KB Output is correct
11 Correct 279 ms 3552 KB Output is correct
12 Correct 240 ms 3544 KB Output is correct
13 Runtime error 5 ms 5424 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -