| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 848909 | ilhan_arda | 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")
#include "race.h"
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
//~ typedef long long ll;
typedef tuple<int, int, int> iii;
int rem, ans=1e9, k;
vector<vector<pair<int, int>>> graph;
vector<int> sub;
map<int, int> sums;
vector<bool> vis, mark;
int dfs1(int node, int par){
int val= 1;
mark[node]=true;
//~ cout<<node<<" :dfs1: "<<par<<endl;
for(auto it: graph[node]){
if(it.fi==par)continue;
if(vis[it.fi])continue;
val+=dfs1(it.fi, node);
}
sub[node]=val;
return val;
}
void dfs2(int node, int par, int cur, int len){
if(cur>k)return;
//~ cout<<node<<" :dfs2: "<<cur<<" :dfs2: "<<len<<endl;
if(sums[k-cur] || cur==k){
//~ cout<<"ans "<< ans <<" ans"<<endl;
ans=min(ans, sums[k-cur]+len);
//~ cout<<ans<<" :: "<<node<<" :: "<<cur<<" :: "<<len<<endl;
}
for(auto it: graph[node]){
if(vis[it.fi])continue;
if(it.fi==par)continue;
dfs2(it.fi, node, cur+it.se, len+1);
}
if(!sums[cur])sums[cur]=len;
sums[cur]=min(len, sums[cur]);
return;
}
int findcentroid(int node, int par, int sz){
for(auto it: graph[node]){
//~ cout<<"findcentroid"<<endl;
if(vis[it.fi])continue;
if(it.fi==par)continue;
if(sub[it.fi]>=sz){
return findcentroid(it.fi, node, sz);
}
}
return node;
}
int best_path(int N, int K, int H[][2], int L[])
{
rem = N;
k=K;
graph.assign(N+5, vector<pair<int, int>>());
vis.assign(N+5, false);
for(int i=0;i<N-1;i++){
graph[H[i][1]].pb({H[i][0], L[i]});
graph[H[i][0]].pb({H[i][1], L[i]});
}
while(rem){
mark.assign(N+5, false);
//~ sums.assign(1e6+5, -1);
sub.assign(N+5, 0);
for(int i=0;i<N;i++){
//~ sums.assign(1e6+5, -1);
sums.clear();
if(mark[i] || vis[i])continue;
int sz=dfs1(i, -1);
int centroid=findcentroid(i, -1, sz);
//~ cout<<centroid<<" ::::: "<<endl;
dfs2(centroid, -1, 0, 0);
vis[centroid]=true;
rem--;
}
}
if(ans==1e9)return -1;
return ans;
return N;
}