# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
78955 | 2018-10-09T18:28:00 Z | Charis02 | Paprike (COI18_paprike) | C++14 | 90 ms | 46184 KB |
#include<iostream> #include<stdio.h> #include<vector> #include<cmath> #include<queue> #include<string.h> #include<map> #include<set> #include<algorithm> #define ll long long #define pi pair < ll,ll > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define N 100004 #define INF 1e9+7 using namespace std; ll n,k,h[N],cuts,a,b; ll val[N]; vector < vector < ll > > graph(N); void calc(ll cur,ll par) { priority_queue < ll > pq; rep(i,0,graph[cur].size()) { if(graph[cur][i] == par) continue; calc(graph[cur][i],cur); pq.push(-val[graph[cur][i]]); } val[cur] = h[cur]; while(!pq.empty()) { ll to_add = -pq.top(); pq.pop(); if(to_add + val[cur] > k) break; cuts--; val[cur] += to_add; } return; } int main() { ios_base::sync_with_stdio(false); cin >> n >> k; rep(i,1,n+1) { cin >> h[i]; } rep(i,0,n-1) { cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } cuts = n-1; calc(1,1); cout << cuts << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2936 KB | Output is correct |
3 | Correct | 4 ms | 2996 KB | Output is correct |
4 | Correct | 4 ms | 2996 KB | Output is correct |
5 | Correct | 4 ms | 2996 KB | Output is correct |
6 | Correct | 4 ms | 2996 KB | Output is correct |
7 | Correct | 4 ms | 2996 KB | Output is correct |
8 | Correct | 4 ms | 2996 KB | Output is correct |
9 | Correct | 4 ms | 2996 KB | Output is correct |
10 | Correct | 4 ms | 3144 KB | Output is correct |
11 | Correct | 4 ms | 3144 KB | Output is correct |
12 | Correct | 4 ms | 3144 KB | Output is correct |
13 | Correct | 4 ms | 3144 KB | Output is correct |
14 | Correct | 4 ms | 3144 KB | Output is correct |
15 | Correct | 4 ms | 3216 KB | Output is correct |
16 | Correct | 4 ms | 3216 KB | Output is correct |
17 | Correct | 4 ms | 3216 KB | Output is correct |
18 | Correct | 4 ms | 3236 KB | Output is correct |
19 | Correct | 4 ms | 3240 KB | Output is correct |
20 | Correct | 4 ms | 3288 KB | Output is correct |
21 | Correct | 5 ms | 3440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 71 ms | 21224 KB | Output is correct |
2 | Correct | 69 ms | 23132 KB | Output is correct |
3 | Correct | 71 ms | 25260 KB | Output is correct |
4 | Correct | 70 ms | 27256 KB | Output is correct |
5 | Correct | 65 ms | 29124 KB | Output is correct |
6 | Correct | 68 ms | 31064 KB | Output is correct |
7 | Correct | 68 ms | 32988 KB | Output is correct |
8 | Correct | 62 ms | 34528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2936 KB | Output is correct |
3 | Correct | 4 ms | 2996 KB | Output is correct |
4 | Correct | 4 ms | 2996 KB | Output is correct |
5 | Correct | 4 ms | 2996 KB | Output is correct |
6 | Correct | 4 ms | 2996 KB | Output is correct |
7 | Correct | 4 ms | 2996 KB | Output is correct |
8 | Correct | 4 ms | 2996 KB | Output is correct |
9 | Correct | 4 ms | 2996 KB | Output is correct |
10 | Correct | 4 ms | 3144 KB | Output is correct |
11 | Correct | 4 ms | 3144 KB | Output is correct |
12 | Correct | 4 ms | 3144 KB | Output is correct |
13 | Correct | 4 ms | 3144 KB | Output is correct |
14 | Correct | 4 ms | 3144 KB | Output is correct |
15 | Correct | 4 ms | 3216 KB | Output is correct |
16 | Correct | 4 ms | 3216 KB | Output is correct |
17 | Correct | 4 ms | 3216 KB | Output is correct |
18 | Correct | 4 ms | 3236 KB | Output is correct |
19 | Correct | 4 ms | 3240 KB | Output is correct |
20 | Correct | 4 ms | 3288 KB | Output is correct |
21 | Correct | 5 ms | 3440 KB | Output is correct |
22 | Correct | 5 ms | 34528 KB | Output is correct |
23 | Correct | 5 ms | 34528 KB | Output is correct |
24 | Correct | 4 ms | 34528 KB | Output is correct |
25 | Correct | 5 ms | 34528 KB | Output is correct |
26 | Correct | 5 ms | 34528 KB | Output is correct |
27 | Correct | 4 ms | 34528 KB | Output is correct |
28 | Correct | 5 ms | 34528 KB | Output is correct |
29 | Correct | 5 ms | 34528 KB | Output is correct |
30 | Correct | 4 ms | 34528 KB | Output is correct |
31 | Correct | 4 ms | 34528 KB | Output is correct |
32 | Correct | 5 ms | 34528 KB | Output is correct |
33 | Correct | 4 ms | 34528 KB | Output is correct |
34 | Correct | 4 ms | 34528 KB | Output is correct |
35 | Correct | 5 ms | 34528 KB | Output is correct |
36 | Correct | 4 ms | 34528 KB | Output is correct |
37 | Correct | 5 ms | 34528 KB | Output is correct |
38 | Correct | 4 ms | 34528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2936 KB | Output is correct |
3 | Correct | 4 ms | 2996 KB | Output is correct |
4 | Correct | 4 ms | 2996 KB | Output is correct |
5 | Correct | 4 ms | 2996 KB | Output is correct |
6 | Correct | 4 ms | 2996 KB | Output is correct |
7 | Correct | 4 ms | 2996 KB | Output is correct |
8 | Correct | 4 ms | 2996 KB | Output is correct |
9 | Correct | 4 ms | 2996 KB | Output is correct |
10 | Correct | 4 ms | 3144 KB | Output is correct |
11 | Correct | 4 ms | 3144 KB | Output is correct |
12 | Correct | 4 ms | 3144 KB | Output is correct |
13 | Correct | 4 ms | 3144 KB | Output is correct |
14 | Correct | 4 ms | 3144 KB | Output is correct |
15 | Correct | 4 ms | 3216 KB | Output is correct |
16 | Correct | 4 ms | 3216 KB | Output is correct |
17 | Correct | 4 ms | 3216 KB | Output is correct |
18 | Correct | 4 ms | 3236 KB | Output is correct |
19 | Correct | 4 ms | 3240 KB | Output is correct |
20 | Correct | 4 ms | 3288 KB | Output is correct |
21 | Correct | 5 ms | 3440 KB | Output is correct |
22 | Correct | 71 ms | 21224 KB | Output is correct |
23 | Correct | 69 ms | 23132 KB | Output is correct |
24 | Correct | 71 ms | 25260 KB | Output is correct |
25 | Correct | 70 ms | 27256 KB | Output is correct |
26 | Correct | 65 ms | 29124 KB | Output is correct |
27 | Correct | 68 ms | 31064 KB | Output is correct |
28 | Correct | 68 ms | 32988 KB | Output is correct |
29 | Correct | 62 ms | 34528 KB | Output is correct |
30 | Correct | 5 ms | 34528 KB | Output is correct |
31 | Correct | 5 ms | 34528 KB | Output is correct |
32 | Correct | 4 ms | 34528 KB | Output is correct |
33 | Correct | 5 ms | 34528 KB | Output is correct |
34 | Correct | 5 ms | 34528 KB | Output is correct |
35 | Correct | 4 ms | 34528 KB | Output is correct |
36 | Correct | 5 ms | 34528 KB | Output is correct |
37 | Correct | 5 ms | 34528 KB | Output is correct |
38 | Correct | 4 ms | 34528 KB | Output is correct |
39 | Correct | 4 ms | 34528 KB | Output is correct |
40 | Correct | 5 ms | 34528 KB | Output is correct |
41 | Correct | 4 ms | 34528 KB | Output is correct |
42 | Correct | 4 ms | 34528 KB | Output is correct |
43 | Correct | 5 ms | 34528 KB | Output is correct |
44 | Correct | 4 ms | 34528 KB | Output is correct |
45 | Correct | 5 ms | 34528 KB | Output is correct |
46 | Correct | 4 ms | 34528 KB | Output is correct |
47 | Correct | 64 ms | 34528 KB | Output is correct |
48 | Correct | 67 ms | 34528 KB | Output is correct |
49 | Correct | 64 ms | 34528 KB | Output is correct |
50 | Correct | 63 ms | 34528 KB | Output is correct |
51 | Correct | 79 ms | 34528 KB | Output is correct |
52 | Correct | 90 ms | 36548 KB | Output is correct |
53 | Correct | 85 ms | 38264 KB | Output is correct |
54 | Correct | 80 ms | 40180 KB | Output is correct |
55 | Correct | 76 ms | 41684 KB | Output is correct |
56 | Correct | 82 ms | 43096 KB | Output is correct |
57 | Correct | 49 ms | 46184 KB | Output is correct |