Submission #1202176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202176		namhh	Race (IOI11_race)	C++20	0 / 100	26 ms	55156 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e6+1;
int n,k,sz[N],len[N],mx = 0,ans = 1e9;
vector<pii>adj[N];
bool del[N];
int dfs(int u, int p){
	sz[u] = 1;
	for(auto v : adj[u]){
		if(v.fi == p || del[v.fi]) continue;
		sz[u] += dfs(v.fi,u);
	}
	return sz[u];
}
int get_centroid(int u, int p, int con){
	for(auto v : adj[u]) 
	    if(v.fi != p && !del[v.fi] && sz[v.fi] > con/2) return get_centroid(v.fi,u,con);
	return u;
}
void dem(int u, int p, bool type, int h, int cc = 1){
	if(h > k) return;
	mx = max(mx,h);
	if(type) len[h] = min(len[h],cc);
	else ans = min(ans,cc+len[k-h]);
    //cout << u << " " << p << " " << h << "\n";
	for(auto v : adj[u]) 
	    if(v.fi != p && !del[v.fi]) dem(v.fi,u,type,h+v.se,cc+1);
}
void cd(int u){
	int centroid = get_centroid(u,-1,dfs(u,-1));
	del[centroid] = true;
	len[0] = 0;
	mx = 0;
	for(auto v : adj[centroid]){
		if(!del[v.fi]){
			dem(v.fi,centroid,0,v.se);
			dem(v.fi,centroid,1,v.se);
		}
	}
	fill(len,len+mx+1,1e9);
	for(auto v : adj[centroid]) if(!del[v.fi]) cd(v.fi);
}

int best_path(int N, int K, int h[][2], int l[]) {
	n = N, k = K;
	for(int i = 0; i < n - 1; i++){
		adj[h[i][1]].push_back({h[i][2], l[i]});
		adj[h[i][2]].push_back({h[i][1], l[i]});
	}
	for(int i = 0; i <= 2000000; i++) len[i] = 1e9;
	cd(0);
	if(ans == 1e9) return -1;
	else return ans;
}

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