# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
693273 | 2023-02-02T14:33:46 Z | vuavisao | Paprike (COI18_paprike) | C++14 | 73 ms | 38316 KB |
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define ll long long using namespace std; const ll N = 1e6 + 10; ll n, k; ll a[N]; vector<ll> g[N]; ll cost[N]; ll res; void dfs(ll u, ll p) { cost[u] = a[u]; for(const auto& v : g[u]) { if(v == p) continue; dfs(v, u); } sort(g[u].begin(), g[u].end(), [&] (ll lhs, ll rhs) -> bool { return cost[lhs] < cost[rhs]; }); ll need = (ll) g[u].size(); for(const auto& v : g[u]) { if(v == p) { -- need; continue; } if(cost[u] + cost[v] <= k) { cost[u] += cost[v]; -- need; } } res += need; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("COI18_PAPRIKE.inp", "r")) { freopen("COI18_PAPRIKE.inp", "r", stdin); freopen("COI18_PAPRIKE.out", "w", stdout); } cin >> n >> k; for(ll i = 1; i <= n; ++ i) cin >> a[i]; for(ll i = 2; i <= n; ++ i) { ll u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); cout << res; return 0; } /// Code by vuavisao
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23824 KB | Output is correct |
2 | Correct | 15 ms | 23816 KB | Output is correct |
3 | Correct | 13 ms | 23820 KB | Output is correct |
4 | Correct | 14 ms | 23824 KB | Output is correct |
5 | Correct | 14 ms | 23812 KB | Output is correct |
6 | Correct | 16 ms | 23764 KB | Output is correct |
7 | Correct | 14 ms | 23824 KB | Output is correct |
8 | Correct | 14 ms | 23824 KB | Output is correct |
9 | Correct | 12 ms | 23760 KB | Output is correct |
10 | Correct | 12 ms | 23764 KB | Output is correct |
11 | Correct | 14 ms | 23788 KB | Output is correct |
12 | Correct | 14 ms | 23700 KB | Output is correct |
13 | Correct | 16 ms | 23788 KB | Output is correct |
14 | Correct | 14 ms | 23764 KB | Output is correct |
15 | Correct | 14 ms | 23764 KB | Output is correct |
16 | Correct | 14 ms | 23824 KB | Output is correct |
17 | Correct | 12 ms | 23764 KB | Output is correct |
18 | Correct | 14 ms | 23764 KB | Output is correct |
19 | Correct | 12 ms | 23820 KB | Output is correct |
20 | Correct | 17 ms | 23764 KB | Output is correct |
21 | Correct | 14 ms | 23720 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 38224 KB | Output is correct |
2 | Correct | 51 ms | 38204 KB | Output is correct |
3 | Correct | 52 ms | 38316 KB | Output is correct |
4 | Correct | 55 ms | 38240 KB | Output is correct |
5 | Correct | 52 ms | 38220 KB | Output is correct |
6 | Correct | 52 ms | 38220 KB | Output is correct |
7 | Correct | 52 ms | 38192 KB | Output is correct |
8 | Correct | 48 ms | 37772 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23824 KB | Output is correct |
2 | Correct | 15 ms | 23816 KB | Output is correct |
3 | Correct | 13 ms | 23820 KB | Output is correct |
4 | Correct | 14 ms | 23824 KB | Output is correct |
5 | Correct | 14 ms | 23812 KB | Output is correct |
6 | Correct | 16 ms | 23764 KB | Output is correct |
7 | Correct | 14 ms | 23824 KB | Output is correct |
8 | Correct | 14 ms | 23824 KB | Output is correct |
9 | Correct | 12 ms | 23760 KB | Output is correct |
10 | Correct | 12 ms | 23764 KB | Output is correct |
11 | Correct | 14 ms | 23788 KB | Output is correct |
12 | Correct | 14 ms | 23700 KB | Output is correct |
13 | Correct | 16 ms | 23788 KB | Output is correct |
14 | Correct | 14 ms | 23764 KB | Output is correct |
15 | Correct | 14 ms | 23764 KB | Output is correct |
16 | Correct | 14 ms | 23824 KB | Output is correct |
17 | Correct | 12 ms | 23764 KB | Output is correct |
18 | Correct | 14 ms | 23764 KB | Output is correct |
19 | Correct | 12 ms | 23820 KB | Output is correct |
20 | Correct | 17 ms | 23764 KB | Output is correct |
21 | Correct | 14 ms | 23720 KB | Output is correct |
22 | Correct | 14 ms | 23784 KB | Output is correct |
23 | Correct | 14 ms | 23836 KB | Output is correct |
24 | Correct | 17 ms | 23820 KB | Output is correct |
25 | Correct | 16 ms | 23836 KB | Output is correct |
26 | Correct | 13 ms | 23836 KB | Output is correct |
27 | Correct | 13 ms | 23816 KB | Output is correct |
28 | Correct | 14 ms | 23764 KB | Output is correct |
29 | Correct | 13 ms | 23776 KB | Output is correct |
30 | Correct | 13 ms | 23876 KB | Output is correct |
31 | Correct | 17 ms | 23836 KB | Output is correct |
32 | Correct | 16 ms | 23896 KB | Output is correct |
33 | Correct | 13 ms | 23812 KB | Output is correct |
34 | Correct | 14 ms | 23824 KB | Output is correct |
35 | Correct | 13 ms | 23776 KB | Output is correct |
36 | Correct | 14 ms | 23840 KB | Output is correct |
37 | Correct | 13 ms | 23764 KB | Output is correct |
38 | Correct | 14 ms | 23892 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23824 KB | Output is correct |
2 | Correct | 15 ms | 23816 KB | Output is correct |
3 | Correct | 13 ms | 23820 KB | Output is correct |
4 | Correct | 14 ms | 23824 KB | Output is correct |
5 | Correct | 14 ms | 23812 KB | Output is correct |
6 | Correct | 16 ms | 23764 KB | Output is correct |
7 | Correct | 14 ms | 23824 KB | Output is correct |
8 | Correct | 14 ms | 23824 KB | Output is correct |
9 | Correct | 12 ms | 23760 KB | Output is correct |
10 | Correct | 12 ms | 23764 KB | Output is correct |
11 | Correct | 14 ms | 23788 KB | Output is correct |
12 | Correct | 14 ms | 23700 KB | Output is correct |
13 | Correct | 16 ms | 23788 KB | Output is correct |
14 | Correct | 14 ms | 23764 KB | Output is correct |
15 | Correct | 14 ms | 23764 KB | Output is correct |
16 | Correct | 14 ms | 23824 KB | Output is correct |
17 | Correct | 12 ms | 23764 KB | Output is correct |
18 | Correct | 14 ms | 23764 KB | Output is correct |
19 | Correct | 12 ms | 23820 KB | Output is correct |
20 | Correct | 17 ms | 23764 KB | Output is correct |
21 | Correct | 14 ms | 23720 KB | Output is correct |
22 | Correct | 70 ms | 38224 KB | Output is correct |
23 | Correct | 51 ms | 38204 KB | Output is correct |
24 | Correct | 52 ms | 38316 KB | Output is correct |
25 | Correct | 55 ms | 38240 KB | Output is correct |
26 | Correct | 52 ms | 38220 KB | Output is correct |
27 | Correct | 52 ms | 38220 KB | Output is correct |
28 | Correct | 52 ms | 38192 KB | Output is correct |
29 | Correct | 48 ms | 37772 KB | Output is correct |
30 | Correct | 14 ms | 23784 KB | Output is correct |
31 | Correct | 14 ms | 23836 KB | Output is correct |
32 | Correct | 17 ms | 23820 KB | Output is correct |
33 | Correct | 16 ms | 23836 KB | Output is correct |
34 | Correct | 13 ms | 23836 KB | Output is correct |
35 | Correct | 13 ms | 23816 KB | Output is correct |
36 | Correct | 14 ms | 23764 KB | Output is correct |
37 | Correct | 13 ms | 23776 KB | Output is correct |
38 | Correct | 13 ms | 23876 KB | Output is correct |
39 | Correct | 17 ms | 23836 KB | Output is correct |
40 | Correct | 16 ms | 23896 KB | Output is correct |
41 | Correct | 13 ms | 23812 KB | Output is correct |
42 | Correct | 14 ms | 23824 KB | Output is correct |
43 | Correct | 13 ms | 23776 KB | Output is correct |
44 | Correct | 14 ms | 23840 KB | Output is correct |
45 | Correct | 13 ms | 23764 KB | Output is correct |
46 | Correct | 14 ms | 23892 KB | Output is correct |
47 | Correct | 56 ms | 33520 KB | Output is correct |
48 | Correct | 54 ms | 32264 KB | Output is correct |
49 | Correct | 54 ms | 31916 KB | Output is correct |
50 | Correct | 55 ms | 31612 KB | Output is correct |
51 | Correct | 60 ms | 31048 KB | Output is correct |
52 | Correct | 58 ms | 31088 KB | Output is correct |
53 | Correct | 59 ms | 30992 KB | Output is correct |
54 | Correct | 57 ms | 30896 KB | Output is correct |
55 | Correct | 73 ms | 30532 KB | Output is correct |
56 | Correct | 69 ms | 30528 KB | Output is correct |
57 | Correct | 45 ms | 30856 KB | Output is correct |