Submission #1167355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167355		SG2Alok	Race (IOI11_race)	C++20	100 / 100	352 ms	30532 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second

int sz[200005], mins[1000005];
bool vis[200005];
vector<pair<int, int>> adj[200005];
int ans = 1e9, k;

int dfs(int u, int par){
	if(vis[u]) return 0;
	
	sz[u] = 1;
	for(auto v: adj[u]){
		if(v.fi != par){
			sz[u] += dfs(v.fi, u);
		}
	}
	
	return sz[u];
}

int ctr(int u, int par, int szz){
	for(auto v: adj[u]){
		if(v.fi == par) continue;
		if(!vis[v.fi] && sz[v.fi] * 2 > szz){
			return ctr(v.fi, u, szz);
		}
	}
	
	return u;
}

void get_ans(int u, int par, int len, int dep){
	if(len > k) return;
	ans = min(ans, mins[k - len] + dep);
	
	for(auto v: adj[u]){
		if(!vis[v.fi] && v.fi != par){
			get_ans(v.fi, u, len + v.se, dep + 1);
		}
	}
}

void dfs2(int u, int par, int len, int dep, int tp){
	if(len > k) return;
	if(tp) mins[len] = min(mins[len], dep);
	else mins[len] = 1e9;
	
	for(auto v: adj[u]){
		if(!vis[v.fi] && v.fi != par){
			dfs2(v.fi, u, len + v.se, dep + 1, tp);
		}
	}
}

void ctr_dcmp(int u){
	int cntr = ctr(u, -1, dfs(u, -1));
	
	for(auto v: adj[cntr]){
		if(!vis[v.fi]){
			get_ans(v.fi, cntr, v.se, 1);
			dfs2(v.fi, cntr, v.se, 1, 1);
		}
	}
	
	for(auto v: adj[cntr]){
		if(!vis[v.fi]){
			dfs2(v.fi, cntr, v.se, 1, 0);
		}
	}
	
	vis[cntr] = true;
	
	for(auto v: adj[cntr]){
		if(!vis[v.fi]){
			ctr_dcmp(v.fi);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	k = K;
	for(int i = 0; i < N - 1; i++){
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	
	for(int i = 1; i <= K; i++) mins[i] = 1e9;
	mins[0] = 0;
	
	ctr_dcmp(0);
	
	if(ans == 1e9) ans = -1;
	return ans;
}

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