| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 867410 | HuyQuang_re_Zero | 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 <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#include "race.h"
using namespace std;
map <ll,ll> mp,in4[N];
vector <II> a[N];
ll h[N],w[N],sz[N],i,u,v,m,res;
const ll oo=round(1e18);
void dfs(int u,int p)
{
sz[u]=1;
for(II adj:a[u])
{
int v=adj.fst;
if(v!=p)
{
h[v]=h[u]+1,w[v]=w[u]+adj.snd;
dfs(v,u),sz[u]+=sz[v];
}
}
}
//wu+wv-2*wlca=m
//=>wv=m+2*wlca-wu
void cal(ll wu,ll hu,int lca)
{
// if(lca==6 && hu==2 && wu==6)
if(mp.count(m+2*w[lca]-wu))
res=min(res,hu+mp[m+2*w[lca]-wu]-2*h[lca]);
}
void add(ll w,ll h)
{
if(!mp.count(w)) mp[w]=h;
else mp[w]=min(mp[w],h);
}
void DFS(int u,int p)
{
int x=0;
for(II adj:a[u])
{
int v=adj.fst;
if(v!=p && sz[x]<sz[v]) x=v;
}
for(II adj:a[u])
{
int v=adj.fst;
if(v!=p && v!=x)
{
DFS(v,u);
in4[v]=mp; mp.clear();
}
}
if(x>0) DFS(x,u);
cal(w[u],h[u],u); add(w[u],h[u]);
for(II adj:a[u])
{
int v=adj.fst;
if(v==p || v==x) continue;
for(auto x:in4[v]) cal(x.fst,x.snd,u);
for(auto x:in4[v]) add(x.fst,x.snd);
}
}
ll best_path(int N,int K,int H[][2],int L[])
{
m=K;
for(i=0;i<N-1;i++)
{
int u=H[i][0]+1,v=H[i][1]+1,k=L[i];
// cerr<<u<<" "<<v<<'\n';
a[u].push_back({ v,k });
a[v].push_back({ u,k });
}
res=oo;
dfs(1,0);
DFS(1,0);
return (res==oo) ? -1 : res;
}
/*
int main()
{
freopen("race.inp","r",stdin);
freopen("race.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
int H[n+1][2],L[n+1];
for(int i=0;i<n-1;i++) cin>>H[i][0]>>H[i][1]>>L[i];
cout<<best_path(n,m,H,L);
}
*/