# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
242650 | 2020-06-28T14:46:15 Z | vanic | Paprike (COI18_paprike) | C++14 | 97 ms | 17656 KB |
#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <set> #include <stack> #include <vector> using namespace std; const int maxn=1e5+5; int val[maxn]; vector < int > ms[maxn]; int sol; int n, k; int dfs(int x, int prosl){ vector < int > svi; for(int i=0; i<ms[x].size(); i++){ if(ms[x][i]!=prosl){ svi.push_back(dfs(ms[x][i], x)); } } sort(svi.begin(), svi.end()); int poc=val[x]; for(int i=0; i<svi.size(); i++){ if(poc+svi[i]<=k){ poc+=svi[i]; } else{ sol+=svi.size()-i; break; } } return poc; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; for(int i=0; i<n; i++){ cin >> val[i]; } int x, y; for(int i=0; i<n-1; i++){ cin >> x >> y; x--; y--; ms[x].push_back(y); ms[y].push_back(x); } dfs(0, 0); cout << sol << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2688 KB | Output is correct |
2 | Correct | 6 ms | 2688 KB | Output is correct |
3 | Correct | 6 ms | 2688 KB | Output is correct |
4 | Correct | 6 ms | 2688 KB | Output is correct |
5 | Correct | 7 ms | 2688 KB | Output is correct |
6 | Correct | 6 ms | 2688 KB | Output is correct |
7 | Correct | 6 ms | 2688 KB | Output is correct |
8 | Correct | 6 ms | 2688 KB | Output is correct |
9 | Correct | 6 ms | 2688 KB | Output is correct |
10 | Correct | 6 ms | 2688 KB | Output is correct |
11 | Correct | 6 ms | 2688 KB | Output is correct |
12 | Correct | 6 ms | 2688 KB | Output is correct |
13 | Correct | 6 ms | 2688 KB | Output is correct |
14 | Correct | 6 ms | 2688 KB | Output is correct |
15 | Correct | 6 ms | 2688 KB | Output is correct |
16 | Correct | 6 ms | 2688 KB | Output is correct |
17 | Correct | 6 ms | 2648 KB | Output is correct |
18 | Correct | 6 ms | 2688 KB | Output is correct |
19 | Correct | 6 ms | 2688 KB | Output is correct |
20 | Correct | 6 ms | 2688 KB | Output is correct |
21 | Correct | 6 ms | 2688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 68 ms | 17528 KB | Output is correct |
2 | Correct | 66 ms | 17656 KB | Output is correct |
3 | Correct | 65 ms | 17596 KB | Output is correct |
4 | Correct | 62 ms | 17528 KB | Output is correct |
5 | Correct | 72 ms | 17528 KB | Output is correct |
6 | Correct | 71 ms | 17528 KB | Output is correct |
7 | Correct | 64 ms | 17528 KB | Output is correct |
8 | Correct | 62 ms | 17144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2688 KB | Output is correct |
2 | Correct | 6 ms | 2688 KB | Output is correct |
3 | Correct | 6 ms | 2688 KB | Output is correct |
4 | Correct | 6 ms | 2688 KB | Output is correct |
5 | Correct | 7 ms | 2688 KB | Output is correct |
6 | Correct | 6 ms | 2688 KB | Output is correct |
7 | Correct | 6 ms | 2688 KB | Output is correct |
8 | Correct | 6 ms | 2688 KB | Output is correct |
9 | Correct | 6 ms | 2688 KB | Output is correct |
10 | Correct | 6 ms | 2688 KB | Output is correct |
11 | Correct | 6 ms | 2688 KB | Output is correct |
12 | Correct | 6 ms | 2688 KB | Output is correct |
13 | Correct | 6 ms | 2688 KB | Output is correct |
14 | Correct | 6 ms | 2688 KB | Output is correct |
15 | Correct | 6 ms | 2688 KB | Output is correct |
16 | Correct | 6 ms | 2688 KB | Output is correct |
17 | Correct | 6 ms | 2648 KB | Output is correct |
18 | Correct | 6 ms | 2688 KB | Output is correct |
19 | Correct | 6 ms | 2688 KB | Output is correct |
20 | Correct | 6 ms | 2688 KB | Output is correct |
21 | Correct | 6 ms | 2688 KB | Output is correct |
22 | Correct | 7 ms | 2816 KB | Output is correct |
23 | Correct | 6 ms | 2816 KB | Output is correct |
24 | Correct | 6 ms | 2688 KB | Output is correct |
25 | Correct | 6 ms | 2688 KB | Output is correct |
26 | Correct | 6 ms | 2688 KB | Output is correct |
27 | Correct | 6 ms | 2816 KB | Output is correct |
28 | Correct | 7 ms | 2688 KB | Output is correct |
29 | Correct | 6 ms | 2688 KB | Output is correct |
30 | Correct | 6 ms | 2816 KB | Output is correct |
31 | Correct | 7 ms | 2688 KB | Output is correct |
32 | Correct | 6 ms | 2688 KB | Output is correct |
33 | Correct | 6 ms | 2688 KB | Output is correct |
34 | Correct | 6 ms | 2816 KB | Output is correct |
35 | Correct | 7 ms | 2816 KB | Output is correct |
36 | Correct | 7 ms | 2688 KB | Output is correct |
37 | Correct | 6 ms | 2688 KB | Output is correct |
38 | Correct | 6 ms | 2688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2688 KB | Output is correct |
2 | Correct | 6 ms | 2688 KB | Output is correct |
3 | Correct | 6 ms | 2688 KB | Output is correct |
4 | Correct | 6 ms | 2688 KB | Output is correct |
5 | Correct | 7 ms | 2688 KB | Output is correct |
6 | Correct | 6 ms | 2688 KB | Output is correct |
7 | Correct | 6 ms | 2688 KB | Output is correct |
8 | Correct | 6 ms | 2688 KB | Output is correct |
9 | Correct | 6 ms | 2688 KB | Output is correct |
10 | Correct | 6 ms | 2688 KB | Output is correct |
11 | Correct | 6 ms | 2688 KB | Output is correct |
12 | Correct | 6 ms | 2688 KB | Output is correct |
13 | Correct | 6 ms | 2688 KB | Output is correct |
14 | Correct | 6 ms | 2688 KB | Output is correct |
15 | Correct | 6 ms | 2688 KB | Output is correct |
16 | Correct | 6 ms | 2688 KB | Output is correct |
17 | Correct | 6 ms | 2648 KB | Output is correct |
18 | Correct | 6 ms | 2688 KB | Output is correct |
19 | Correct | 6 ms | 2688 KB | Output is correct |
20 | Correct | 6 ms | 2688 KB | Output is correct |
21 | Correct | 6 ms | 2688 KB | Output is correct |
22 | Correct | 68 ms | 17528 KB | Output is correct |
23 | Correct | 66 ms | 17656 KB | Output is correct |
24 | Correct | 65 ms | 17596 KB | Output is correct |
25 | Correct | 62 ms | 17528 KB | Output is correct |
26 | Correct | 72 ms | 17528 KB | Output is correct |
27 | Correct | 71 ms | 17528 KB | Output is correct |
28 | Correct | 64 ms | 17528 KB | Output is correct |
29 | Correct | 62 ms | 17144 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 6 ms | 2816 KB | Output is correct |
32 | Correct | 6 ms | 2688 KB | Output is correct |
33 | Correct | 6 ms | 2688 KB | Output is correct |
34 | Correct | 6 ms | 2688 KB | Output is correct |
35 | Correct | 6 ms | 2816 KB | Output is correct |
36 | Correct | 7 ms | 2688 KB | Output is correct |
37 | Correct | 6 ms | 2688 KB | Output is correct |
38 | Correct | 6 ms | 2816 KB | Output is correct |
39 | Correct | 7 ms | 2688 KB | Output is correct |
40 | Correct | 6 ms | 2688 KB | Output is correct |
41 | Correct | 6 ms | 2688 KB | Output is correct |
42 | Correct | 6 ms | 2816 KB | Output is correct |
43 | Correct | 7 ms | 2816 KB | Output is correct |
44 | Correct | 7 ms | 2688 KB | Output is correct |
45 | Correct | 6 ms | 2688 KB | Output is correct |
46 | Correct | 6 ms | 2688 KB | Output is correct |
47 | Correct | 68 ms | 11640 KB | Output is correct |
48 | Correct | 63 ms | 10104 KB | Output is correct |
49 | Correct | 62 ms | 9464 KB | Output is correct |
50 | Correct | 65 ms | 9208 KB | Output is correct |
51 | Correct | 66 ms | 8312 KB | Output is correct |
52 | Correct | 66 ms | 8312 KB | Output is correct |
53 | Correct | 77 ms | 8260 KB | Output is correct |
54 | Correct | 97 ms | 8136 KB | Output is correct |
55 | Correct | 66 ms | 7672 KB | Output is correct |
56 | Correct | 92 ms | 7736 KB | Output is correct |
57 | Correct | 46 ms | 9072 KB | Output is correct |