| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 848464 | blacktulip | Race (IOI11_race) | C++17 | 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>
#include "race.h"
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
//~ #define int long long
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 100000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 1000005;
const lo mod = 1000000007;
lo n,m,b[li],a[li],k,flag,t,sub[li],vis[li],cevap=inf,say,last[li],visit[li];
lo cev;
//~ unordered_map<lo,lo> last,visit;
string s;
vector<PII> v[li];
vector<int> vect;
random_device rd;
mt19937 mt(rd());
inline void boya(int node,int ata,lo co){
if(co<=k){
visit[co]=0;
visit[k-co]=0;
}
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
boya(go,node,co+v[node][i].se);
}
if(co<=k){
visit[co]=0;
visit[k-co]=0;
}
}
inline void dfs(lo node,lo ata){
sub[node]=1;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
dfs(go,node);
sub[node]+=sub[go];
}
}
inline void find_centroid(lo node,lo ata,lo sz){
//~ int mx=0;
//~ int ind=0;
vect.pb(node);
for(lo i=0;i<(lo)v[node].size();i++){
int go=v[node][i].fi;
if(vis[go]==1)continue;
if(go==ata)continue;
find_centroid(go,node,sz);
}
//~ return node;
}
inline void dfs2(lo node,lo ata,lo der,lo co){
for(lo i=0;i<(lo)v[node].size();i++){
lo go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
dfs2(go,node,der+1,co+v[node][i].se);
}
if(co<=k){
if(visit[k-co]==1){
cevap=min(cevap,last[k-co]+der);
}
}
}
inline void dfs1(lo node,lo ata,lo der,lo co){
for(lo i=0;i<(lo)v[node].size();i++){
lo go=v[node][i].fi;
if(go==ata)continue;
if(vis[go]==1)continue;
dfs1(go,node,der+1,co+v[node][i].se);
}
if(co<=k){
if(visit[co]==0)last[co]=der;
visit[co]=1;
last[co]=min(last[co],der);
}
}
inline void solve(lo node){
//~ say++;
//~ cout<<say<<endl;
//~ FOR sub[node]=0;
//~ last.clear();
//~ for(int i=0;i<=k;i++)visit[i]=0;
dfs(node,-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
find_centroid(node,-1,sub[node]);
int ab=uniform_int_distribution<int>(0, vect.size()-1)(rng);
lo c=vect[ab];
boya(c,-1,0);
for(lo i=0;i<(lo)v[c].size();i++) {
int go=v[c][i].first;
if(vis[go]) continue ;
dfs2(go,c,1,v[c][i].second);
dfs1(go,c,1,v[c][i].second);
}
if(visit[k]==1)
cevap=min(cevap,last[k]);
vis[c]=1;
//~ cout<<c<<endl;
//~ dfs()
for(lo i=0;i<(lo)v[c].size();i++){
if(vis[v[c][i].fi]==0)solve(v[c][i].fi);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
//~ scanf("%lld %lld",&n,&k);
for(int i=0;i<N-1;i++){
//~ int x,y,z;
//~ scanf("%lld %lld %lld",&x,&y,&z);
v[H[i][0]].pb(mp(H[i][1],L[i]));
v[H[i][1]].pb(mp(H[i][0],L[i]));
}
solve(0);
if(cevap>=inf)cevap=-1;
return cevap;
}