| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 782735 | vjudge1 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "race.h"
#define int long long int
const int N = 2e5+37;
int mi = 1e18, n, k, p;
vector<array<int, 2>> adj[N];
vector<int> vis(N), s(N), vis2(N);
map<int, array<int, 2>> best[2], mp;
void dfs(int v){
vis[v] = 1;
int pf=0;
s[v] = 1;
for(auto i: adj[v]){
if(vis2[i[0]]||vis[i[0]]) continue;
pf++;
dfs(i[0]); s[v]+=s[i[0]];
}
}
int dfs2(int v){
vis[v] = 0;
for(auto i: adj[v]){
if(vis2[i[0]]||!vis[i[0]]) continue;
if(s[i[0]]>=n/2) return dfs2(i[0]);
}
return v;
}
void dfs3(int v, int dist, int z, int f){
// cout<<v<<" "<<dist<<" "<<z<<"\n";
if(!mp.count(dist)||mp[dist]>(array<int, 2>){z, v}){
mp[dist] ={z, v};
}
vis[v] = f;
for(auto i: adj[v]){
if(vis[i[0]]==f||vis2[i[0]]) continue;
dfs3(i[0], dist+i[1], z+1, f);
}
}
void dfs4(int v){
vis[v] = 1;
for(auto pf: adj[v]){
if(vis2[pf[0]]) continue;
mp.clear();
vis[v] = pf[0]+1;
dfs3(pf[0], pf[1], 1, pf[0]+1);
for(auto [i, l]: mp){
if(!best[0].count(i)){
best[0][i] = l;
}
else if(best[0][i]>l){
swap(l, best[0][i]);
if(!best[1].count(i)||best[1][i]>l){
best[1][i]=l;
}
}
else if(!best[1].count(i)||best[1][i]>l){
best[1][i]=l;
}
}
}
}
void gh(int v){
dfs(v);
int x = dfs2(v);
// x is our centroid
//cout<<x<<"\n";
dfs4(x);
for(auto [i, l]: best[0]){
if(!best[0].count(k-i)||vis[l[1]]==vis[best[0][k-i][1]]){
if(!best[1].count(k-i)) continue;
mi=min(mi, best[1][k-i][0]+best[0][i][0]);
}
else{
mi = min(mi, best[0][k-i][0]+best[0][i][0]);
}
}
if(best[0].count(k))
mi=min(mi, best[0][k][0]);
vis2[x]=1, p++;
}
int best_path(int N, int K, int a[][2], int l[]){
n = N, k = K;
for(int i= 0; i < n-1; i++){
int x=a[i][0], y=a[i][1], z=l[i];
adj[x].push_back({y, z});
adj[y].push_back({x, z});
}
p=1;
while(p){
p=0;
fill(vis.begin(), vis.end(), 0);
for(int i = 0; i < n; i++)
if(!vis[i]&&!vis2[i]) gh(i);
}
if(mi==1e18) return -1;
return mi;
}
/*
signed main()
{
//f();
int n, k; cin >> n >> k;
int a[n-1][2], l[n-1];
for(int i=0; i<n-1; i++){
cin>>a[i][0]>>a[i][1] >> l[i];
}
cout<< best_path(n, k, a, l);
}*/