| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 617793 | 2022-08-01T14:25:02 Z | vitkute | Dynamite (POI11_dyn) | C++17 | 311 ms | 29356 KB |
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
template<class X, class Y> bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template<class X, class Y> bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 3e5 + 11;
const int LOG = (int) 20;
int n, m;
int a[maxn], dp[maxn];
vector<int> adj[maxn];
ii s[maxn];
void DFS(int u = 1, int par = -1){
s[u] = {a[u], u};
if(par != -1) s[u].first += a[par];
for(int v : adj[u]) if(v != par){
s[u].first += a[v];
DFS(v, u);
}
}
bool comp(const ii &x, const ii &y){
return (x.first > y.first || (x.first == y.first && a[x.second] > a[y.second]));
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TASK ""
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].PB(v);
adj[v].PB(u);
}
DFS();
sort(s + 1, s + n + 1, comp);
memset(dp, -1, sizeof dp);
queue<int> que;
for(int i = 1; i <= m; i++){
que.push(s[i].second);
dp[s[i].second] = 0;
}
while(!que.empty()){
int u = que.front(); que.pop();
for(int v : adj[u]){
if(dp[v] == -1){
dp[v] = dp[u] + 1;
que.push(v);
}
}
}
int res = 0;
for(int i = 1; i <= n; i++) if(a[i]) maximize(res, dp[i]);
cout << res;
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 5 ms | 8532 KB | Output is correct |
| 2 | Correct | 5 ms | 8532 KB | Output is correct |
| 3 | Correct | 5 ms | 8532 KB | Output is correct |
| 4 | Incorrect | 5 ms | 8540 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 6 ms | 8532 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 6 ms | 8572 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 6 ms | 8552 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 8 ms | 9044 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 31 ms | 11728 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 70 ms | 14400 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 184 ms | 20336 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 311 ms | 28092 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 293 ms | 29356 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |