| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 115752 | YazanZk | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll ;
using namespace std;
const int N = 200005;
vector < pair < int , int > > G[N];
int sub[N] , par[N];
bool blocked[N];
int n , k ;
void get_size(int u, int p){
par[u] = p ;
sub[u] = 1 ;
for(auto ch : G[u]){
int v = ch.first;
if(v == p || blocked[v]) continue ;
get_size(v , u);
sub[u] += sub[v];
}
}
set < pair < int , int > > se;
int dfs(int u , int p , ll w , int d){
if(w > k) return n ;
int ret = n ;
auto it = *se.lower_bound({k - w , 0});
if(it.first == k - w)
ret = d + it.second ;
for(auto ch : G[u]){
int v = ch.first , ww = ch.second ;
if(v == p || blocked[v]) continue ;
ret = min(ret , dfs(v , u , w + ww , d + 1));
}
return ret ;
}
void update(int u , int p , ll w , int d){
se.insert({w , d});
for(auto ch : G[u]){
int v = ch.first , ww = ch.second ;
if(v == p || blocked[v]) continue ;
update(v , u , w + ww , d + 1);
}
}
int solve(int u){
se.clear() ;
int ret = n ;
for(auto ch : G[u]){
int v = ch.first , w = ch.second ;
if(blocked[v]) continue ;
ret = min(ret , dfs(v , u , w , 1));
update(v , u , w , 1);
}
return ret;
}
int get_centroid(int src){
get_size(src , src);
queue < int > Q ;
Q.push(src);
int centroid = src , best = sub[src];
while(!Q.empty()){
int u = Q.front();
Q.pop();
int size = sub[src] - sub[u];
for(auto ch : G[u]){
int v = ch.first;
if(v == par[u] || blocked[v]) continue ;
Q.push(v);
size = max(size , sub[v]);
}
if(best > size){
best = size ;
centroid = u ;
}
}
blocked[centroid] = true ;
int ret = solve(centroid);
for(auto ch : G[centroid]){
int v = ch.first;
if(blocked[v]) continue ;
ret = min(ret , get_centroid(v));
}
return ret;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k ;
vector < pair < int , int > > ve ;
for(int i = 0 ; i < n - 1 ; i++){
int u , v ;
cin >> u >> v ;
ve.push_back({u , v});
}
for(auto i : ve){
int x ; cin >> x ;
G[i.first].push_back({i.second , x});
G[i.second].push_back({i.first , x});
}
int ans = get_centroid(0);
if(ans == n) ans = -1 ;
cout << ans << endl ;
return 0;
}