Submission #1054372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054372		ihceker	Race (IOI11_race)	C++14	0 / 100	3073 ms	2396 KiB

race

#include<bits/stdc++.h>
#include"race.h"
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int best_path(int n,int k,int h[][2],int l[]){
	vector<vector<pair<int,int>>>adj(n);
	for(int i=0;i<n-1;i++){
		adj[h[i][0]].pb({h[i][1],l[i]});
		adj[h[i][1]].pb({h[i][0],l[i]});
	}
	vector<int>vis(n),sub(n);
	auto dfs=[&](int node,int p,auto&& dfs)->void{
		sub[node]=1;
		for(auto i:adj[node]){
			if(vis[i.ff] || i.ff==p)continue;
			dfs(i.ff,node,dfs);
			sub[node]+=sub[i.ff];
		}
		return;
	};
	vector<int>cnt(k+1,-1);
	auto dfs2=[&](int node,int p,int dep,int len,vector<pair<int,int>>&depths,auto&& dfs2)->void{
		depths.pb({len,dep});
		for(auto i:adj[node]){
			if(vis[i.ff] || i.ff==p)continue;
			dfs2(i.ff,node,dep+1,len+i.ss,depths,dfs2);
		}
		return;
	};
	auto get_centroid=[&](int node)->int{
		bool end=false;
		int p=-1,sz=sub[node];
		while(!end){
			end=true;
			for(auto i:adj[node]){
				if(vis[i.ff] || i.ff==p || sub[i.ff]<=sz/2)continue;
				p=node;
				node=i.ff;
				end=false;
			}
		}
		return node;
	};
	int ans=2e9;
	auto calc=[&](int node,auto&& calc)->void{
		vis[node]=1;
		vector<vector<pair<int,int>>>depths;
		for(auto i:adj[node]){
			if(!vis[i.ff]){
				depths.pb(vector<pair<int,int>>{});
				dfs2(i.ff,node,1,i.ss,depths.back(),dfs2);
			}
		}
		cnt[0]=0;
		for(auto i:depths){
			for(auto j:i){
				if(j.ff>k)continue;
				if(cnt[k-j.ff]!=-1){
					ans=min(ans,j.ss+cnt[k-j.ff]);
				}
			}
			for(auto j:i){
				if(j.ff>k)continue;
				if(cnt[j.ff]==-1)cnt[j.ff]=j.ss;
				else cnt[j.ff]=min(cnt[j.ff],j.ss);
			}
		}
		for(auto i:depths){
			for(auto j:i){
				if(j.ff>k)continue;
				cnt[j.ff]=-1;
			}
		}
		for(auto i:adj[node]){
			if(vis[i.ff])continue;
			dfs(i.ff,node,dfs);
			int v=get_centroid(i.ff);
			calc(v,calc);
		}
	};
	int s=get_centroid(0);
	calc(s,calc);
	return (ans==2e9?-1:ans);
}

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