Submission #849287

#	Time	Username	Problem	Language	Result	Execution time	Memory
849287		manhtuan22007	Race (IOI11_race)	C++14	21 / 100	73 ms	176464 KiB

race

#include<bits/stdc++.h>
using namespace std;

#define name "race"
#define ll long long
//#define int long long

int n , k;
vector<vector<pair<int , int>>> g(200010);

namespace sub12{
	
	const int maxn = 1e3 + 10;
	
	int par[maxn][11] , h[maxn] , cost[maxn];
	
	void dfs(int u){
		for(auto e : g[u]){
			int v = e.first;
			if(v == par[u][0]) continue;
			h[v] = h[u] + 1;
			cost[v] = cost[u] + e.second;
			par[v][0] = u;
			for(int i = 1 ; i < 11 ; i ++){
				par[v][i] = par[par[v][i - 1]][i - 1];
			}
			dfs(v);
		}
	}
	
	int lca(int u , int v){
		if(h[u] < h[v]) swap(u , v);
		int k = h[u] - h[v];
		for(int i = 0 ; (1 << i) <= k ; i ++){
			if(k >> i & 1) u = par[u][i];
		}
		if(u == v) return u;
		for(int i = 10 ; i >= 0 ; i --){
			if(par[u][i] != par[v][i]){
				u = par[u][i] , v = par[v][i];
			}
		}
		return par[u][0];
	}
	
	int solve(int n , int k){
		dfs(1);
		int res = -1;
		for(int i = 1 ; i <= n ; i ++) for(int j = i + 1 ; j <= n ; j ++){
			int p = lca(i , j);
			int d = cost[i] + cost[j] - 2 * cost[p];
			int num = h[i] + h[j] - 2 * h[p];
			if(d == k) res = (res == -1 ? num : min(res , num));
		}
		return res;
	}
}

namespace sub3{
	
	const int maxn = 2e5 + 10;
	
	int dp[maxn][205] , k;
	
	void dfs(int u , int p){
		dp[u][0] = 0;
		for(auto e : g[u]){
			int v = e.first;
			if(v == p) continue;
			dfs(v , u);
			for(int i = 0 ; i <= k ; i ++){
				if(i + e.second <= k) dp[u][i + e.second] = min(dp[u][i + e.second] , dp[v][i] + 1);
			}
		}
	}
	
	int solve(int n , int k){
		k = k;
		memset(dp , 0x3f , sizeof dp);
		int inf = dp[0][0];
		dfs(1 , 0);
		int res = -1;
		for(int i = 1 ; i <= n ; i ++){
			if(dp[i][k] == inf) continue;
			res = (res == -1 ? dp[i][k] : min(res , dp[i][k]));
		}
		return res;
	}
}

int best_path(int n , int k , int h[][2] , int l[]){
	for(int i = 0 ; i < n - 1 ; i ++){
		int u = h[i][0] , v = h[i][1];
		++u , ++v;
		g[u].push_back({v , l[i]});
		g[v].push_back({u , l[i]});
	}
	if(n <= 1000) return sub12::solve(n , k);
	else if(k <= 100) return sub3::solve(n , k);
}

// int main(){
	// int n , k;
	// cin >> n>> k;
	// int h[20][2] , l[20];
	// for(int i = 0 ; i < n - 1 ; i ++){
		// cin >> h[i][0] >> h[i][1] >> l[i];
	// }
	// cout << best_path(n , k , h , l);
// }
// 

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^

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