| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 3158 | club4208 | Race (IOI11_race) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
#include<cstdio>
#include<algorithm>
#define MAX_N 500000
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define fi first
#define se second
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const int MX = 200005, MG = 400005, INF = 1000000000;
int n, k, ans;
int head[MX], next[MG], to[MG], co[MG], g;
void edge(int a, int b, int c){
next[g] = head[a]; head[a] = g; to[g] = b; co[g++] = c;
}
bool cent[MX];
int sub[MX];
P d[1000005], o[MX]; int di, oi;
void csub(int v, int p){
sub[v] = 1;
for(int i = head[v]; i != -1; i = next[i]){
if(cent[to[i]] || to[i] == p) continue;
csub(to[i],v);
sub[v] += sub[to[i]];
}
}
P ccen(int v, int p, int t){
P m = P(INF,-1);
int x = t-sub[v];
for(int i = head[v]; i != -1; i = next[i]){
if(cent[to[i]] || to[i] == p) continue;
m = min(m,ccen(to[i],v,t));
x = max(x,sub[to[i]]);
}
return min(m,P(x,v));
}
void enu(int v, int p, int dis, int city){
if(dis > k) return;
o[oi++] = P(dis,city);
for(int i = head[v]; i != -1; i = next[i]){
if(cent[to[i]] || to[i] == p) continue;
enu(to[i],v,dis+co[i],city+1);
}
}
void sol(int v){
csub(v,-1);
int c = ccen(v,-1,sub[v]).se;
cent[c] = true;
for(int i = head[c]; i != -1; i = next[i]){
if(cent[to[i]]) continue;
sol(to[i]);
}
di--;
d[0] = P(di,0);
for(int i = head[c]; i != -1; i = next[i]){
if(cent[to[i]]) continue;
oi = 0;
enu(to[i],c,co[i],1);
rep(j,oi){
int x = k-o[j].fi;
if(x >= 0 && d[x].fi == di) ans = min(ans,d[x].se+o[j].se);
}
rep(j,oi) d[o[j].fi] = min(d[o[j].fi], P(di,o[j].se));
}
cent[c] = false;
}
int best_path(int N, int K, int h[MAX_N][2], int l[MAX_N]){
n = N; k = K;
rep(i,n) head[i] = -1;
rep(i,n-1){ edge(h[i][0],h[i][1],l[i]); edge(h[i][1],h[i][0],l[i]);}
ans = INF;
di = 1;
sol(0);
return ans==INF?-1:ans;
}