# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
43989 |
2018-03-29T08:32:15 Z |
wasyl |
Paprike (COI18_paprike) |
C++11 |
|
124 ms |
44132 KB |
#include <bits/stdc++.h>
#ifndef dbg
#define dbg(...)
#endif
#define all(x) begin(x), end(x)
#define rsz(...) resize(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define prt(...) print(cout, __VA_ARGS__)
#define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__)
#define dprt(...) dbg(print(cerr,__VA_ARGS__))
#define ddmp(...) dbg(dmp(__VA_ARGS__))
using namespace std;using ll=long long;
template<typename t>using V=vector<t>;
template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';}
template<typename t, typename... A>void print
(ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);}
int n, k, r;
V< ll > val;
V< V< int > > gr;
inline void dfs (int v, int o)
{
for (int s : gr[v])
if (s != o)
dfs(s, v);
V< int > ilo;
for (int s : gr[v])
if (s != o)
{
val[v] += val[s];
ilo.psh(val[s]);
}
sort(all(ilo));
reverse(all(ilo));
int pt = 0;
while (val[v] > k)
{
val[v] -= ilo[pt++];
++r;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
gr.rsz(n + 1);
val.rsz(n + 1);
for (int i = 1; i <= n; ++i)
cin >> val[i];
for (int i = 0; i < n - 1; ++i)
{
int p, q; cin >> p >> q;
gr[p].psh(q);
gr[q].psh(p);
}
dfs(1, 1);
prt(r);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
360 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
496 KB |
Output is correct |
5 |
Correct |
2 ms |
692 KB |
Output is correct |
6 |
Correct |
2 ms |
692 KB |
Output is correct |
7 |
Correct |
2 ms |
692 KB |
Output is correct |
8 |
Correct |
2 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
692 KB |
Output is correct |
10 |
Correct |
2 ms |
692 KB |
Output is correct |
11 |
Correct |
2 ms |
692 KB |
Output is correct |
12 |
Correct |
2 ms |
780 KB |
Output is correct |
13 |
Correct |
2 ms |
780 KB |
Output is correct |
14 |
Correct |
2 ms |
780 KB |
Output is correct |
15 |
Correct |
2 ms |
780 KB |
Output is correct |
16 |
Correct |
2 ms |
780 KB |
Output is correct |
17 |
Correct |
2 ms |
780 KB |
Output is correct |
18 |
Correct |
2 ms |
780 KB |
Output is correct |
19 |
Correct |
2 ms |
780 KB |
Output is correct |
20 |
Correct |
2 ms |
780 KB |
Output is correct |
21 |
Correct |
2 ms |
780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
15224 KB |
Output is correct |
2 |
Correct |
71 ms |
17236 KB |
Output is correct |
3 |
Correct |
64 ms |
19212 KB |
Output is correct |
4 |
Correct |
66 ms |
21260 KB |
Output is correct |
5 |
Correct |
63 ms |
23244 KB |
Output is correct |
6 |
Correct |
65 ms |
25184 KB |
Output is correct |
7 |
Correct |
64 ms |
27100 KB |
Output is correct |
8 |
Correct |
62 ms |
28504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
360 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
496 KB |
Output is correct |
5 |
Correct |
2 ms |
692 KB |
Output is correct |
6 |
Correct |
2 ms |
692 KB |
Output is correct |
7 |
Correct |
2 ms |
692 KB |
Output is correct |
8 |
Correct |
2 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
692 KB |
Output is correct |
10 |
Correct |
2 ms |
692 KB |
Output is correct |
11 |
Correct |
2 ms |
692 KB |
Output is correct |
12 |
Correct |
2 ms |
780 KB |
Output is correct |
13 |
Correct |
2 ms |
780 KB |
Output is correct |
14 |
Correct |
2 ms |
780 KB |
Output is correct |
15 |
Correct |
2 ms |
780 KB |
Output is correct |
16 |
Correct |
2 ms |
780 KB |
Output is correct |
17 |
Correct |
2 ms |
780 KB |
Output is correct |
18 |
Correct |
2 ms |
780 KB |
Output is correct |
19 |
Correct |
2 ms |
780 KB |
Output is correct |
20 |
Correct |
2 ms |
780 KB |
Output is correct |
21 |
Correct |
2 ms |
780 KB |
Output is correct |
22 |
Correct |
3 ms |
28504 KB |
Output is correct |
23 |
Correct |
3 ms |
28504 KB |
Output is correct |
24 |
Correct |
2 ms |
28504 KB |
Output is correct |
25 |
Correct |
3 ms |
28504 KB |
Output is correct |
26 |
Correct |
3 ms |
28504 KB |
Output is correct |
27 |
Correct |
2 ms |
28504 KB |
Output is correct |
28 |
Correct |
3 ms |
28504 KB |
Output is correct |
29 |
Correct |
2 ms |
28504 KB |
Output is correct |
30 |
Correct |
3 ms |
28504 KB |
Output is correct |
31 |
Correct |
2 ms |
28504 KB |
Output is correct |
32 |
Correct |
2 ms |
28504 KB |
Output is correct |
33 |
Correct |
2 ms |
28504 KB |
Output is correct |
34 |
Correct |
3 ms |
28504 KB |
Output is correct |
35 |
Correct |
3 ms |
28504 KB |
Output is correct |
36 |
Correct |
3 ms |
28504 KB |
Output is correct |
37 |
Correct |
3 ms |
28504 KB |
Output is correct |
38 |
Correct |
2 ms |
28504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
360 KB |
Output is correct |
3 |
Correct |
2 ms |
472 KB |
Output is correct |
4 |
Correct |
2 ms |
496 KB |
Output is correct |
5 |
Correct |
2 ms |
692 KB |
Output is correct |
6 |
Correct |
2 ms |
692 KB |
Output is correct |
7 |
Correct |
2 ms |
692 KB |
Output is correct |
8 |
Correct |
2 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
692 KB |
Output is correct |
10 |
Correct |
2 ms |
692 KB |
Output is correct |
11 |
Correct |
2 ms |
692 KB |
Output is correct |
12 |
Correct |
2 ms |
780 KB |
Output is correct |
13 |
Correct |
2 ms |
780 KB |
Output is correct |
14 |
Correct |
2 ms |
780 KB |
Output is correct |
15 |
Correct |
2 ms |
780 KB |
Output is correct |
16 |
Correct |
2 ms |
780 KB |
Output is correct |
17 |
Correct |
2 ms |
780 KB |
Output is correct |
18 |
Correct |
2 ms |
780 KB |
Output is correct |
19 |
Correct |
2 ms |
780 KB |
Output is correct |
20 |
Correct |
2 ms |
780 KB |
Output is correct |
21 |
Correct |
2 ms |
780 KB |
Output is correct |
22 |
Correct |
65 ms |
15224 KB |
Output is correct |
23 |
Correct |
71 ms |
17236 KB |
Output is correct |
24 |
Correct |
64 ms |
19212 KB |
Output is correct |
25 |
Correct |
66 ms |
21260 KB |
Output is correct |
26 |
Correct |
63 ms |
23244 KB |
Output is correct |
27 |
Correct |
65 ms |
25184 KB |
Output is correct |
28 |
Correct |
64 ms |
27100 KB |
Output is correct |
29 |
Correct |
62 ms |
28504 KB |
Output is correct |
30 |
Correct |
3 ms |
28504 KB |
Output is correct |
31 |
Correct |
3 ms |
28504 KB |
Output is correct |
32 |
Correct |
2 ms |
28504 KB |
Output is correct |
33 |
Correct |
3 ms |
28504 KB |
Output is correct |
34 |
Correct |
3 ms |
28504 KB |
Output is correct |
35 |
Correct |
2 ms |
28504 KB |
Output is correct |
36 |
Correct |
3 ms |
28504 KB |
Output is correct |
37 |
Correct |
2 ms |
28504 KB |
Output is correct |
38 |
Correct |
3 ms |
28504 KB |
Output is correct |
39 |
Correct |
2 ms |
28504 KB |
Output is correct |
40 |
Correct |
2 ms |
28504 KB |
Output is correct |
41 |
Correct |
2 ms |
28504 KB |
Output is correct |
42 |
Correct |
3 ms |
28504 KB |
Output is correct |
43 |
Correct |
3 ms |
28504 KB |
Output is correct |
44 |
Correct |
3 ms |
28504 KB |
Output is correct |
45 |
Correct |
3 ms |
28504 KB |
Output is correct |
46 |
Correct |
2 ms |
28504 KB |
Output is correct |
47 |
Correct |
62 ms |
28504 KB |
Output is correct |
48 |
Correct |
64 ms |
28504 KB |
Output is correct |
49 |
Correct |
64 ms |
29600 KB |
Output is correct |
50 |
Correct |
65 ms |
31516 KB |
Output is correct |
51 |
Correct |
124 ms |
32880 KB |
Output is correct |
52 |
Correct |
85 ms |
34840 KB |
Output is correct |
53 |
Correct |
91 ms |
36680 KB |
Output is correct |
54 |
Correct |
93 ms |
38724 KB |
Output is correct |
55 |
Correct |
79 ms |
40048 KB |
Output is correct |
56 |
Correct |
88 ms |
41452 KB |
Output is correct |
57 |
Correct |
46 ms |
44132 KB |
Output is correct |