| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 712948 | anhduc2701 | 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.
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include "race.h"
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) (ll)(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x) (1LL<<(x))
#define task "tnc"
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,k;
vector<pair<int,int>>G[maxn];
int sz[maxn];
int ok[maxn];
int h[maxn];
int h1[maxn];
map<int,int>p;
int ans=1e9;
void dfs(int u,int pa){
sz[u]=1;
for(auto v:G[u]){
if(v.fi==pa || ok[v.fi]==1)continue;
dfs(v.fi,u);
sz[u]+=sz[v.fi];
}
}
int fin(int u,int pa,int siz){
for(auto v:G[u]){
if(v.fi==pa || ok[v.fi]==1)continue;
if(sz[v.fi]>siz/2)return fin(v.fi,u,siz);
}
return u;
}
void dfs1(int u,int pa){
if(h[u]==k){
ans=min(ans,h1[u]);
}
if(p.find(k-h[u])!=p.end()){
ans=min(ans,p[k-h[u]]+h1[u]);
}
for(auto v:G[u]){
if(v.fi==pa || ok[v.fi]==1)continue;
h[v.fi]=h[u]+v.se;
h1[v.fi]=h[u]+1;
dfs1(v.fi,u);
}
}
void dfs2(int u,int pa){
if(p[h[u]]==0){
p[h[u]]=h1[u];
}
else{
p[h[u]]=min(p[h[u]],h1[u]);
}
for(auto v:G[u]){
if(v.fi==pa|| ok[v.fi]==1)continue;
dfs2(v.fi,u);
}
}
void build(int u,int pa){
dfs(u,pa);
int cen=fin(u,pa,sz[u]);
ok[cen]=1;
h[cen]=0;
h1[cen]=0;
p.clear();
for(int i=0;i<len(G[cen]);i++){
int v=G[cen][i].fi;
if(v==pa || ok[v]==1)continue;
h[v]=G[cen][i].se;
h1[v]=1;
dfs1(v,cen);
dfs2(v,cen);
}
p.clear();
h[cen]=0;
h1[cen]=0;
for(int i=(long long)(G[cen].size())-1;i>=0;i--){
int v=G[cen][i].fi;
if(v==pa || ok[v]==1)continue;
h[v]=G[cen][i].se;
h1[v]=1;
dfs1(v,cen);
dfs2(v,cen);
}
for(auto v:G[cen]){
if(v.fi==pa || ok[v.fi]==1)continue;
build(v.fi,cen);
}
}
int best_path(int N,int K,int (*h)[2],int *l){
cin.tie(0),cout.tie(0)->sync_with_stdio(0);
//freopen(task".inp" , "r" , stdin);
//freopen(task".out" , "w" , stdout);
n=N;
k=K;
for(int i=0;i<n-1;i++){
int u,v,w;
u=h[i][0];
v=h[i][1];
w=l[i];
u++;
v++;
G[u].pb({v,w});
G[v].pb({u,w});
}
build(1,-1);
if(ans==1e9+5){
return -1;
}
else{
return ans;
}
}