Submission #1316893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316893		exoworldgd	Race (IOI11_race)	C++20	0 / 100	1 ms	332 KiB

race

#include<bits/stdc++.h>
#define ll long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
const int N=2e5+5,K=1e6+5;
vector<array<int,2>>g[N];
int n,k,ans=1e9,sz[N],mn[K],del[N];
int dfs_sz(int u,int p){
	sz[u]=1;
	for(auto[v,w]:g[u])if(v!=p&&!del[v])sz[u]+=dfs_sz(v,u);
	return sz[u];
}
int centroid(int u,int p,int tot){
	for(auto[v,w]:g[u])if(v!=p&&!del[v]&&sz[v]*2>tot)return centroid(v,u,tot);
	return u;
}
void dfs(int u,int p,int d,int e,vector<array<int,2>>&paths){
	if(d>k)return;
	paths.push_back({d,e});
	for(auto [v,w]:g[u])if(v!=p&&!del[v])dfs(v,u,d+w,e+1,paths);
}
void solve(int u){
	int c=centroid(u,-1,dfs_sz(u,-1));
	del[c]=1;
	vector<vector<array<int,2>>>all;
	for(auto[v,w]:g[c]){
		if(del[v])continue;
		vector<array<int,2>>paths;
		dfs(v,c,w,1,paths),all.push_back(paths);
		for(auto[d,e]:paths)if(d<=k)ans=min(ans,mn[k-d]+e);
	}
	for(auto&paths:all)for(auto[d,e]:paths)if(d<=k)mn[d]=min(mn[d],e);
	for(auto&paths:all)for(auto[d,e]:paths)if(d<=k)mn[d]=1e9;
	for(auto[v,w]:g[c])if(!del[v])solve(v);
}
int best_path(int n_,int k_,int h[][2],int *l){
	n=n_,k=k_,fill(mn,mn+k+1,1e9),mn[0]=0;
	for(int i=0;i<n-1;i++)g[h[i][0]].push_back({h[i][1],l[i]}),g[h[i][1]].push_back({h[i][0],l[i]});
	solve(0);
	return ans==1e9?-1:ans;
}

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