| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 339894 | bigDuck | 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 "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
int n, k;
set<pii> g[200010];
bool v[200010];
int res=1e9;
int sz[200010];
void build_sz(int s){
v[s]=true;
sz[s]=1;
for(auto u:g[s]){
if(!v[u.ft]){
build_sz(u.ft);
sz[s]+=sz[u.ft];
}
}
v[s]=false;
return;
}
int c, mx;
void find_centroid(int s, int total){
v[s]=true;
int ac=max(sz[s], total-sz[s]+1);
if(ac<mx){
c=s; mx=ac;
}
int nxt=0, sm=0;
for(pii e:g[s]){
int u=e.ft;
if(!v[u]){find_centroid(u);}
}
v[s]=false;
}
int k1[1000010];
vector<pii> rec;
vector<pii> del;
queue<int> forest;
void path(int s, int l, int h, int c){
v[s]=true;
if((k1[k-l]>0) ){
res=min(res, h+k1[k-l]-1);
}
for(auto pr:g[s]){
int u=pr.ft, d=pr.sc;
if( (!v[u]) && ( (l+d)<=(k) ) ){
path(u, l+d, h+1, c);
if(s==c){
while(!rec.empty()){
del.pb(rec.back());
if(k1[rec.back().ft]==0){
k1[rec.back().ft]=rec.back().sc;
}
else{
k1[rec.back().ft]=min(k1[rec.back().ft], rec.back().sc);
}
rec.pop_back();
}
}
}
}
rec.pb({l, h});
v[s]=false;
if(s==c){
while(!del.empty()){
k1[del.back().ft]=0;
del.pop_back();
}
rec.clear(); del.clear();
}
return ;
}
void subtask_4(){
forest.push(1);
while(!forest.empty()){
int node=forest.front(); forest.pop();
build_sz(node);
if(sz[node]==1){continue;}
mx=1e18;
find_centroid(node, sz[node]);
//cout<<c<<"\n"<<flush;
k1[0]=1;
path(c, 0, 1, c);
for(auto pr:g[c]){
int u=pr.ft, d=pr.sc;
g[u].erase({c, d});
forest.push(u);
}
g[c].clear();
}
}
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]+1, v=H[i][1]+1, d=L[i];
g[u].insert({v, d}); g[v].insert({u, d});
}
subtask_4();
if(res==(1e9)){
return -1;
}
return res-1;
}