| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 922236 | Nurislam | 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 "race.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;
const int inf = 1e9, mxN = 2e5+2;
vii g[mxN];
int us[mxN];
int m, ctr, ans = inf;
int k;
int dfs_sz(int v, int pr){
if(us[v])return 0;
int s = 1;
for(auto [to, cst]:g[v]){
if(to == pr)continue;
s += dfs_sz(to, v);
}
return s;
}
int dfs_ctr(int v, int pr){
if(us[v])return 0;
int s = 1;
bool ok = 1;
for(auto [to, cst]:g[v]){
if(to == pr)continue;
int sto = dfs_ctr(to, v);
if(sto > m/2)ok = 0;
s += sto;
}
if(s < m/2)ok = 0;
if(ok)ctr = v;
return s;
}
map<int,int> mp;
void dfs(int v, int pr, int dep, int sum, bool ok){
if(sum > k)return;
if (!ok){
if ( sum == k ) ans = min(ans, dep);
else ans = min(ans, !mp.count(k-sum) ? inf : mp[k-sum]+dep);
}else{
if ( !mp.count(sum) ) mp[sum] = dep;
else mp[sum] = min(mp[sum], dep);
}
for(auto [to, w]:g[v]){
if (us[to] || to == pr)continue;
dfs(to, v, dep+1, sum+w, ok);
}
}
void fun(int v){
m = dfs_sz(v, -1);
m = dfs_ctr(v, -1);
us[ctr] = 1;
mp.clear();
for(auto [to, cst]:g[ctr]){
if(us[to])continue;
dfs(to, ctr, 1, cst, 0);
dfs(to, ctr, 1, cst, 1);
}
for(auto [to, cst]:g[ctr]){
if(us[to])continue;
fun(to);
}
}
int best_path(int n, int K, int h[][2], int l[])
{
for(int i = 0; i < n-1; i++){
g[h[i][0]].pb({h[i][1], l[i]});
g[h[i][1]].pb({h[i][0], l[i]});
}
k = K;
fun(0);
return (ans == inf?-1:ans);
}