| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 210015 | brcode | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <race.h>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5+5;
long long ans =1e18;
long long sz[MAXN];
bool used[MAXN];
long long n,k;
map<long long,long long> m1;
vector<pair<long long,long long>> toadd;
long long currsz = 0;
vector<pair<long long,long long>> v1[MAXN];
void dfs(long long curr,long long par){
currsz++;
sz[curr] = 1;
for(auto x:v1[curr]){
if(!used[x.first] && x.first!=par){
dfs(x.first,curr);
sz[curr]+=sz[x.first];
}
}
}
long long centroid(long long curr,long long par){
for(auto x:v1[curr]){
if(!used[x.first] && x.first!=par && sz[x.first]>currsz/2){
return centroid(x.first,curr);
}
}
return curr;
}
void dfsans(long long curr,long long par,long long val,long long depth){
for(auto x:v1[curr]){
if(x.first!=par && !used[x.first]){
toadd.push_back(make_pair(val+x.second,depth+1));
dfsans(x.first,curr,val+x.second,depth+1);
}
}
}
void decompose(long long u,long long par){
currsz = 0;
dfs(u,u);
long long cen = centroid(u,u);
//cout<<cen<<endl;
//link[cen] = par;
//find all paths through the centroid
m1.clear();
for(auto x:v1[cen]){
if(!used[x.first]){
toadd.clear();
toadd.push_back(make_pair(x.second,1));
dfsans(x.first,cen,x.second,1);
}
for(auto y:toadd){
if(cen == 1){
// cout<<x.first<<" "<<y.first<<" "<<123<<endl;
}
if(k-y.first>=0 && m1[k-y.first]){
// cout<<cen<<" "<<m1[k-y.first]+y.second<<endl;
ans = min(ans,m1[k-y.first]+y.second);
}
if(y.first == k){
ans = min(ans,y.second);
}
}
for(auto y:toadd){
// cout<<cen<<" "<<y.first<<" "<<y.second<<endl;
if(!m1[y.first]){
m1[y.first] = y.second;
}else{
m1[y.first] = min(m1[y.first],y.second);
}
}
}
used[cen] = true;
for(auto x:v1[cen]){
if(!used[x.first]){
decompose(x.first,cen);
}
}
used[cen] = false;
}
long long best_path(long long N,long long K,long long H[][2],long long L[]){
n = N;
k = K;
for(long long i=0;i<n-1;i++){
long long u = H[i][0];
long long v = H[i][1];
long long w = L[i];
u++;v++;
v1[u].push_back(make_pair(v,w));
v1[v].push_back(make_pair(u,w));
}
decompose(1,1);
if(ans == 1e9){
return -1;
}
return ans;
}