# | 제출 시각UTC-0 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1112389 | VVUU | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N, K, total=1e14;
vector<pair<int, int> > edge[1000010];
int h[1000010];
int siz[1000010];
int wei[1000010];
map<int, int> sav;
void PDF(int n, int cha){
siz[n]=1;
for(auto gg:edge[n]){
int v=gg.first;
int w=gg.second;
if(v==cha) continue;
h[v]=h[n]+1;
wei[v]=wei[n]+w;
PDF(v, n);
siz[n]+=siz[v];
}
}
void get(int n, int cha, int st){
if(wei[n]-2*wei[st]<=K){
int req=K-(wei[n]-2*wei[st]);
if(sav[req]==0) sav[req]=1e14;
total=min(total, h[n]-h[st]+sav[req]-h[st]);
}
for(auto v:edge[n]){
if(v.first==cha) continue;
get(v.first, n, st);