## Submission #116583

# Submission time Handle Problem Language Result Execution time Memory
116583 2019-06-13T03:12:56 Z khulegub Race (IOI11_race) C++14
0 / 100
2 ms 384 KB
```#include "race.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> ii;
vector<vector<ii> > to;
int l[200020];
int k;
int h[200020][2];
int subsz;
int sz[200020];
bool block[200020];
int wt[200020];
map<int,int> bag;
map<int,bool> bagex;
map<int,bool> subbagex;
map<int,int> subbag;
int ans=0;
void dosz(int u,int pre){
sz[u]=1;
for(ii vw : to[u]){
int v=vw.xx;
if(v!=pre&&(!block[v])){
dosz(v,u);
sz[u]+=sz[v];
}
}
}
int findcentr(int u,int pre){
for(ii vw : to[u]){
int v=vw.xx;
if(v!=pre&&(!block[v])){
if(sz[v]>subsz/2) return findcentr(v,u);
}
}
return u;
}
void putwt(int u,int pre,int w,int l){
if(subbagex[w]){
subbag[w]=min(subbag[w],1);
}
else{
subbagex[w]=1;
subbag[w]=l;
}
for(ii vw : to[u]){
int v=vw.xx,ww=vw.yy;
if(v!=pre&&(!block[v])){
putwt(v,u,w+ww,l+1);
}
}
}
void solve(int x){
dosz(x,x);
subsz=sz[x];
int centr=findcentr(x,x);
block[centr]=1;
bag.clear();
for(ii sub : to[centr]){
subbag.clear();
int v=sub.xx,ww=sub.yy;
putwt(v,centr,ww,1);
//K jintei centroid hurtel
if(subbagex[k]) ans=min(ans,subbag[k]);
//bag & subbag
for(auto item : subbag){
int subw=item.xx,subl=item.yy;
if(bagex[k-subw]){
ans=min(subl,bag[k-subl]);
}
}
for(auto item : subbag){ //merge
int subw=item.xx,subl=item.yy;
if(bagex[subw]){
bag[subw]=min(bag[subw],subl);
}
else{
bagex[subw]=1;
bag[subw]=subl;
}
}
}

for(ii vw : to[centr]){
int v=vw.xx;
if(!block[v]){
solve(v);
}
}
}

int best_path(int N, int K, int H[][2], int L[]){
to.assign(N+1,vector<ii>());
k=K;
for(int i=0;i<N-1;i++){
int u=H[i][0],v=H[i][1],w=L[i];
to[u].pb(mp(v,w));
to[v].pb(mp(u,w));
}
solve(1);
// cout << ans << endl;
// cout << "#################################\n";
return ans;
}```

#### Subtask #1 0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #3 0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #4 0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -