# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
77246 | 2018-09-24T09:42:55 Z | farukkastamonuda | Dynamite (POI11_dyn) | C++14 | 1713 ms | 30468 KB |
#include <bits/stdc++.h> #define li 300005 #define mid (bas+son)/2 using namespace std; int n, m, ans, A[li], x, y, say; vector<int> vv[li]; int solve(int node, int ata, int sayi){ int t = 0,v = 0; for(int i = 0;i < (int)vv[node].size();i++){ int go = vv[node][i]; if(ata == go) continue; int u = solve(go,node,sayi); if(u == 0) continue; if(u > 0) v = max(v,u); else t = min(t,u); } if(abs(t) >= sayi){ ans++; return sayi; } if(t == 0 && v == 0) return -A[node]; if(v > abs(t)) return v - 1; return t - 1; } int can(int k){ ans = 0; if(solve(1,0,k) < 0) ans++; if(ans <= m) return 1; return 0; } int main(){ scanf("%d %d",&n,&m); for(int i=1;i <= n;i++) {scanf("%d",&A[i]);say+=A[i];} for(int i=1;i < n;i++){ scanf("%d %d",&x,&y); vv[x].push_back(y); vv[y].push_back(x); } if(say <= m){ printf("0\n"); return 0; } int bas = 1,son = n; while(bas <= son){ if(can(mid) == 1) son = mid - 1; else bas = mid + 1; } printf("%d\n",bas); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7288 KB | Output is correct |
2 | Correct | 8 ms | 7416 KB | Output is correct |
3 | Correct | 8 ms | 7456 KB | Output is correct |
4 | Correct | 9 ms | 7456 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7456 KB | Output is correct |
2 | Correct | 8 ms | 7504 KB | Output is correct |
3 | Correct | 8 ms | 7508 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7516 KB | Output is correct |
2 | Correct | 9 ms | 7652 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7652 KB | Output is correct |
2 | Correct | 8 ms | 7796 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 8216 KB | Output is correct |
2 | Correct | 44 ms | 8964 KB | Output is correct |
3 | Correct | 49 ms | 9652 KB | Output is correct |
4 | Correct | 59 ms | 11196 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 11196 KB | Output is correct |
2 | Correct | 97 ms | 11648 KB | Output is correct |
3 | Correct | 167 ms | 11800 KB | Output is correct |
4 | Correct | 149 ms | 14592 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 165 ms | 14592 KB | Output is correct |
2 | Correct | 159 ms | 14592 KB | Output is correct |
3 | Correct | 266 ms | 14592 KB | Output is correct |
4 | Correct | 305 ms | 17536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 843 ms | 17536 KB | Output is correct |
2 | Correct | 803 ms | 17924 KB | Output is correct |
3 | Correct | 1295 ms | 25216 KB | Output is correct |
4 | Correct | 1287 ms | 25216 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1589 ms | 25216 KB | Output is correct |
2 | Correct | 1077 ms | 25216 KB | Output is correct |
3 | Correct | 1669 ms | 25216 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1619 ms | 28600 KB | Output is correct |
2 | Correct | 1095 ms | 28600 KB | Output is correct |
3 | Correct | 1713 ms | 30468 KB | Output is correct |
4 | Correct | 459 ms | 30468 KB | Output is correct |