# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
748277 | 2023-05-26T03:13:59 Z | Username4132 | Paprike (COI18_paprike) | C++14 | 52 ms | 15584 KB |
#include<iostream> #include<vector> #include<algorithm> using namespace std; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define PB push_back const int MAXN=100010; int n, k, ans, arr[MAXN], par[MAXN], dep[MAXN], order[MAXN]; vector<int> g[MAXN]; void dfs(int v, int p){ par[v]=p; for(int to:g[v]) if(to!=p) { dep[to]=dep[v]+1; dfs(to, v); } } int main(){ scanf("%d %d", &n, &k); forn(i, n) scanf("%d", &arr[i]), order[i]=i; forn(i, n-1){ int a, b; scanf("%d %d", &a, &b); --a, --b; g[a].PB(b), g[b].PB(a); } dfs(0, 0); sort(order, order+n, [](int a, int b){ return dep[a]!=dep[b]? dep[a]>dep[b] : arr[a]<arr[b]; }); forn(i, n-1){ int ind=order[i]; if(arr[ind]+arr[par[ind]]<=k) arr[par[ind]]+=arr[ind]; else ans++; } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2644 KB | Output is correct |
3 | Correct | 2 ms | 2644 KB | Output is correct |
4 | Correct | 2 ms | 2644 KB | Output is correct |
5 | Correct | 1 ms | 2656 KB | Output is correct |
6 | Correct | 1 ms | 2644 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 2 ms | 2644 KB | Output is correct |
9 | Correct | 2 ms | 2644 KB | Output is correct |
10 | Incorrect | 2 ms | 2660 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 15584 KB | Output is correct |
2 | Correct | 47 ms | 15548 KB | Output is correct |
3 | Correct | 47 ms | 15560 KB | Output is correct |
4 | Correct | 52 ms | 15580 KB | Output is correct |
5 | Correct | 46 ms | 15580 KB | Output is correct |
6 | Correct | 44 ms | 15472 KB | Output is correct |
7 | Correct | 45 ms | 15500 KB | Output is correct |
8 | Correct | 44 ms | 14956 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2644 KB | Output is correct |
3 | Correct | 2 ms | 2644 KB | Output is correct |
4 | Correct | 2 ms | 2644 KB | Output is correct |
5 | Correct | 1 ms | 2656 KB | Output is correct |
6 | Correct | 1 ms | 2644 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 2 ms | 2644 KB | Output is correct |
9 | Correct | 2 ms | 2644 KB | Output is correct |
10 | Incorrect | 2 ms | 2660 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2644 KB | Output is correct |
3 | Correct | 2 ms | 2644 KB | Output is correct |
4 | Correct | 2 ms | 2644 KB | Output is correct |
5 | Correct | 1 ms | 2656 KB | Output is correct |
6 | Correct | 1 ms | 2644 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 2 ms | 2644 KB | Output is correct |
9 | Correct | 2 ms | 2644 KB | Output is correct |
10 | Incorrect | 2 ms | 2660 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |