| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 526964 | ar_paixaos19 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int MAXN = 200010;
const int MAXK = 1000010;
int n, k, marc[MAXN], minl[MAXK], sub[MAXN], val[MAXN], prof[MAXN], ultimo[MAXK], cont = 0, resp;
int h[MAXN][2], l[MAXN];
vector<int> grafo[MAXN], peso[MAXN];
int acessa(int pos){
if(ultimo[pos] == cont) return minl[pos];
return INF + 10;
}
void muda(int pos, int valor){
minl[pos] = valor;
ultimo[pos] = cont;
return;
}
void zera(){
cont++;
return;
}
void dfs1(int v, int p){
//printf("X\n");
sub[v] = 1;
for(int i = 0; i < grafo[v].size(); i++){
//printf("v = %d, p = %d\n", v, p);
int viz = grafo[v][i];
if(viz == p) continue;
if(marc[viz] == 1) continue;
dfs1(viz, v);
sub[v] += sub[viz];
}
return;
}
void dfs2(int v, int p){
//printf("Y\n");
muda(val[v], min(acessa(val[v]), prof[v]));
resp = min(resp, prof[v] + acessa(k - val[v]));
for(int i = 0; i < grafo[v].size(); i++){
int viz = grafo[v][i];
if(viz == p) continue;
if(marc[viz] == 1) continue;
val[viz] = val[v] + peso[v][i];
prof[viz] = prof[v] + 1;
//printf("minl[%d] = %d\n", val[viz], acessa(val[viz]));
dfs2(viz, v);
}
return;
}
int findcentroid(int v, int p){
//printf("Z\n");
for(int i = 0; i < grafo[v].size(); i++){
int viz = grafo[v][i];
if(viz == p) continue;
if(marc[viz] == 1) continue;
if(sub[viz] > n / 2) return findcentroid(viz, v);
}
return v;
}
int daq(int v, int p){
dfs1(v, p);
int centroid = findcentroid(v, p);
marc[centroid] = 1;
if(sub[centroid] == 1) return INF;
zera();
resp = INF;
for(int i = 0; i < grafo[centroid].size(); i++){
int viz = grafo[centroid][i];
if(marc[viz] == 1) continue;
val[viz] = peso[centroid][i];
prof[viz] = 1;
dfs2(viz, viz);
}
for(int i = 0; i < grafo[v].size(); i++){
int viz = grafo[v][i];
if(viz == p) continue;
if(marc[viz] == 1) continue;
resp = min(resp, daq(viz, v));
}
//printf("W\n");
return resp;
}
int best_path(int n, int k, int h[][2], int l[]){
for(int i = 0; i < n - 1; i++){
grafo[h[i][0]].push_back(h[i][1]); peso[h[i][0]].push_back(l[i]);
grafo[h[i][1]].push_back(h[i][0]); peso[h[i][1]].push_back(l[i]);
if(l[i] > k){
peso[h[i][0]].pop_back();
peso[h[i][1]].pop_back();
}
}
int resp = daq(0, 0);
if(resp == INF) resp = -1;
return resp;
}
int main(){
scanf("%d %d", &n, &k);
for(int i = 0; i < n - 1; i++){
int u, v, p; scanf("%d %d %d", &u, &v, &p);
h[i][0] = u; h[i][1] = v; l[i] = p;
}
//printf("R\n");
printf("%d\n", best_path(n, k, h, l));
return 0;
}