oj.uz

Submission #1054386

# Submission time Handle Problem Language Result Execution time Memory
1054386 2024-08-12T09:24:10 Z blacktulip Race (IOI11_race) C++17
0 / 100
 2 ms 10332 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> v[200005];
int vis[200005],sub[200005];
map<int,int> mpp;
int k;
int cev;
#define pb push_back
#define fi first
#define se second

inline void pre(int node,int ata){
	sub[node]=1;
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		pre(go.fi,node);
		sub[node]+=sub[go.fi];
	}
}

inline int find_centroid(int node,int ata,int val){
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		if(sub[go.fi]>=val/2)return find_centroid(go.fi,node,val);
	}
	return node;
}

inline void check(int node,int ata,int der,int kac){
	if(der>k)return ;
	if(mpp.find(k-der)!=mpp.end())cev=min(cev,mpp[k-der]+kac);
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		check(go.fi,node,der+go.se,kac+1);
	}
}

inline void build(int node,int ata,int der,int kac){
	if(der>k)return ;
	if(mpp.find(k-der)==mpp.end())mpp[der]=kac;
	else mpp[der]=min(mpp[der],kac);
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		build(go.fi,node,der+go.se,kac+1);
	}
}

inline void sifirla(int node,int ata,int der){
	if(der>k)return ;
	mpp[der]=-1;
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		sifirla(go.fi,node,der+go.se);
	}
}

inline void solve(int c){
	pre(c,-1);
	c=find_centroid(c,-1,sub[c]);
	mpp[0]=0;
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		check(go.fi,c,go.se,1);
		build(go.fi,c,go.se,1);
	}
	//~ for(auto go:v[c]){
		//~ if(vis[go.fi])continue;
		//~ sifirla(go.fi,c,go.se);
	//~ }
	mpp.clear();
	vis[c]=1;
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		solve(go.fi);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	k=K;
	//~ memset(mpp,-1,sizeof(mpp));
	for(int i=0;i<N-1;i++){
		v[H[i][0]].pb({H[i][1],L[i]});
		v[H[i][1]].pb({H[i][0],L[i]});
	}
	cev=N+2;
	solve(0);
	if(cev==N+2)cev=-1;
	return cev;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10332 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 10332 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 10332 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 10332 KB Output isn't correct
2 Halted 0 ms 0 KB -