Submission #964519

#	Time	Username	Problem	Language	Result	Execution time	Memory
964519		UmairAhmadMirza	Race (IOI11_race)	C++14	100 / 100	723 ms	43380 KiB

race

#include <bits/stdc++.h>
using namespace std;
int const MN=200005;
map<int,int> cnt;
vector<pair<int,int>> adj[MN];
int sz[MN];
int n,k;
int ans=MN;
void dfs_sz(int node,int par=-1){
	sz[node]=1;
	for(auto i:adj[node])
		if(i.first!=par){
			dfs_sz(i.first,node);
			sz[node]+=sz[i.first];
		}
}
int total=0;
int find_centroid(int node){
	for(auto i:adj[node]){
		if(sz[i.first]*2>total){
			sz[node]-=sz[i.first];
			sz[i.first]+=sz[node];
			return find_centroid(i.first);
		}
	}
	return node;
}
void dfs(int node,int par,int w,int dep){
	if(w==k)
		ans=min(ans,dep);
	if(w>=k)
		return;
	if(cnt.find(k-w)!=cnt.end())
		ans=min(ans,cnt[k-w]+dep);
	for(auto i:adj[node])
		if(sz[i.first]!=-1 && i.first!=par)
			dfs(i.first,node,w+i.second,dep+1);
}
void update(int node,int par,int w,int dep){
	if(w>=k)
		return;
	if(cnt[w]==0 || cnt[w]>dep)
		cnt[w]=dep;
	for(auto i:adj[node])
		if(sz[i.first]!=-1 && i.first!=par)
			update(i.first,node,w+i.second,dep+1);
}
void solve(int node){
	total=sz[node];
	node=find_centroid(node);
	sz[node]=-1;
	// cout<<node<<endl;
	for(auto i:adj[node]){
		if(sz[i.first]==-1)
			continue;
		dfs(i.first,-1,i.second,1);
		update(i.first,-1,i.second,1);
	}
	cnt.clear();
	// cout<<ans<<endl;
	for(auto i:adj[node])
		if(sz[i.first]!=-1)
			solve(i.first);
}
int best_path(int N, int K, int H[][2], int L[]){
	n=N;
	k=K;
	total=n;
	for (int i = 0; i < n-1; ++i)
	{
		int u=H[i][0];
		int v=H[i][1];
		adj[u].push_back({v,L[i]});
		adj[v].push_back({u,L[i]});
	}
	dfs_sz(0);
	solve(0);
	if(ans==MN)
		ans=-1;
	return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57