| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 129475 | arnold518 | 경주 (Race) (IOI11_race) | C++14 | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int N, K, ans=987654321;
vector<pii> adj[MAXN+10];
int sz[MAXN+10];
bool del[MAXN+10];
map<int, int> M;
void getsz(int now, int bef)
{
sz[now]=1;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
getsz(nxt.first, now);
sz[now]+=sz[nxt.first];
}
}
int getcen(int now, int bef, int tot)
{
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
if(tot/2<sz[nxt.first]) return getcen(nxt.first, now, tot);
}
return now;
}
void dfs(int now, int bef, int dep, int len)
{
if(M.count(K-len)) ans=min(ans, M[K-len]+dep);
if(M.count(len)) M[len]=min(M[len], dep);
else M[len]=dep;
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
if(nxt.first==bef) continue;
if(len+nxt.second>K) continue;
dfs(nxt.first, now, dep+1, len+nxt.second);
}
}
void decomp(int now)
{
getsz(now, now);
now=getcen(now, now, sz[now]);
del[now]=true;
M.clear();
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
dfs(nxt.first, nxt.first, 1, nxt.second);
}
for(pii nxt : adj[now])
{
if(del[nxt.first]) continue;
decomp(nxt.first);
}
}
int best_path(int NN, int KK, int HH[][2], int LL[])
{
int i, j;
N=NN; K=KK;
for(i=0; i+1<N; i++)
{
int u=HH[i][0], v=HH[i][1], w=LL[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
decomp(0);
if(ans==INF) ans=-1;
return ans;
}