oj.uz

Submission #101406

# Submission time Handle Problem Language Result Execution time Memory
101406 2019-03-19T01:06:49 Z dwsc 007 (CEOI14_007) C++14
0 / 100
 1000 ms 525312 KB 
#include <bits/stdc++.h>
using namespace std;
int n,v;
int p[100010];
vector<int> adj[100010];
long long dp(int x,int dist,int pa){
    if (dist == -1) return -1e18;
   // cout << x << " " << dist << " " << pa << '\n';
    long long ans = 0;
    long long sum = 0;
    for (int i = 0; i < (int)(adj[x].size()); i++){
        int nx = adj[x][i];
        if (nx == pa) continue;
        ans = max(ans,dp(nx,dist,x));
        sum += p[nx];
    }
   // cout << sum << "\n";
    ans = max(ans,sum);
    for (int i = 0; i < (int)(adj[x].size()); i++){
        int nx = adj[x][i];
        if (nx == pa) continue;
        ans = max(ans,dp(nx,dist-1,x)+sum-p[nx]);
    }
    return ans;
}
int main(){
    cin >> n >> v;
    for (int i = 0; i < n; i++){
        cin >> p[i];
    }
    for (int i = 0; i < n-1; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if (n <= 1000){
        long long ans = 0;
        for (int i = 0; i < n; i++){
          //  cout << dp(i,v,-1) << "\n";
            ans = max(ans,dp(i,v,-1));
        }
        cout << ans;
    }
    else cout << dp(0,v,-1);
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 955 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 8 ms 5120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 462 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 7 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 398 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 8 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 489 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 944 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 479 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 503 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 8 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 7 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 7 ms 5120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 460 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 10 ms 5120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 540 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 483 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 447 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 9 ms 5120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 416 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 401 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 391 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 476 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 449 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 4472 KB Output isn't correct
2 Runtime error 60 ms 8908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 55 ms 8312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 80 ms 9352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 41 ms 4216 KB Output isn't correct
6 Incorrect 42 ms 4472 KB Output isn't correct
7 Runtime error 61 ms 9128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 58 ms 7760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 490 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Execution timed out 1068 ms 5496 KB Time limit exceeded
11 Incorrect 76 ms 6264 KB Output isn't correct
12 Runtime error 39 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 87 ms 11256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 73 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 53 ms 6620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 38 ms 6568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 40 ms 6608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 42 ms 6576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 40 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 54 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 43 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 44 ms 6748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 42 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 45 ms 6632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 43 ms 6664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 41 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 40 ms 6748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 41 ms 6688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 42 ms 6576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 42 ms 6708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 40 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 39 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 39 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 40 ms 6712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 43 ms 6716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 52 ms 6640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 62 ms 6716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 43 ms 6768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 41 ms 6748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 42 ms 6708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 40 ms 6728 KB Execution killed with signal 11 (could be triggered by violating memory limits)