| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 210011 | brcode | 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 <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int ans =1e9;
int sz[MAXN];
bool used[MAXN];
int n,k;
map<int,int> m1;
vector<pair<int,int>> toadd;
int currsz = 0;
vector<pair<int,int>> v1[MAXN];
void dfs(int curr,int par){
currsz++;
sz[curr] = 1;
for(auto x:v1[curr]){
if(!used[x.first] && x.first!=par){
dfs(x.first,curr);
sz[curr]+=sz[x.first];
}
}
}
int centroid(int curr,int par){
for(auto x:v1[curr]){
if(!used[x.first] && x.first!=par && sz[x.first]>currsz/2){
return centroid(x.first,curr);
}
}
return curr;
}
void dfsans(int curr,int par,int val,int depth){
for(auto x:v1[curr]){
if(x.first!=par && !used[x.first]){
toadd.push_back(make_pair(val+x.second,depth+1));
dfsans(x.first,curr,val+x.second,depth+1);
}
}
}
void decompose(int u,int par){
currsz = 0;
dfs(u,u);
int cen = centroid(u,u);
//cout<<cen<<endl;
//link[cen] = par;
//find all paths through the centroid
m1.clear();
for(auto x:v1[cen]){
if(!used[x.first]){
toadd.clear();
toadd.push_back(make_pair(x.second,1));
dfsans(x.first,cen,x.second,1);
}
for(auto y:toadd){
if(cen == 1){
// cout<<x.first<<" "<<y.first<<" "<<123<<endl;
}
if(k-y.first>0 && m1[k-y.first]){
// cout<<cen<<" "<<m1[k-y.first]+y.second<<endl;
ans = min(ans,m1[k-y.first]+y.second);
}
}
for(auto y:toadd){
// cout<<cen<<" "<<y.first<<" "<<y.second<<endl;
if(!m1[y.first]){
m1[y.first] = y.second;
}else{
m1[y.first] = min(m1[y.first],y.second);
}
}
}
used[cen] = true;
for(auto x:v1[cen]){
if(!used[x.first]){
decompose(x.first,cen);
}
}
used[cen] = false;
}
int best_path(int N,int K,int H[][2],int L[]){
n = N;
k = K;
for(int i=0;i<n-1;i++){
int u = H[i][0];
int v = H[i][1];
int w = L[i];
u++;v++;
v1[u].push_back(make_pair(v,w));
v1[v].push_back(make_pair(u,w));
}
decompose(1,1);
if(ans == 1e9){
return -1;
}
return ans;
}
int main(){
}