제출 #1154766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154766		crispxx	Race (IOI11_race)	C++20	21 / 100	3097 ms	21064 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

// #include "grader.cpp"

#define all(x) x.begin(), x.end()

const int l = 20;

int best_path(int N, int K, int H[][2], int L[]) {
	int n = N, k = K;
	
	vector<vector<pair<int, int>>> adj(n);
	
	for(int i = 0; i < n - 1; i++) {
		auto [u, v] = H[i];
		adj[u].emplace_back(v, L[i]);
		adj[v].emplace_back(u, L[i]);
	}
	
	vector<int> tin(n), tout(n), d(n);
	vector<long long> sd(n);
	
	vector<vector<int>> jmp(n, vector<int>(l + 1));
	
	int timer = 0;
	
	auto dfs = [&](auto &&self, int v, int p) -> void {
		jmp[v][0] = p;
		
		for(int i = 1; i <= l; i++) {
			jmp[v][i] = jmp[ jmp[v][i - 1] ][i - 1];
		}
		
		tin[v] = timer++;
		
		for(auto [to, w] : adj[v]) {
			if(to == p) continue;
			
			sd[to] = sd[v] + w;
			d[to] = d[v] + 1;
			
			self(self, to, v);
		}
		
		tout[v] = timer++;
	};
	
	dfs(dfs, 0, 0);
	
	auto upper = [&](int u, int v) {
		return tin[v] > tin[u] && tout[v] < tout[u];
	};
	
	auto lca = [&](int u, int v) {
		if(upper(u, v)) return u;
		if(upper(v, u)) return v;
		
		for(int i = l; i >= 0; i--) {
			if(!upper(jmp[u][i], v)) u = jmp[u][i];
		}
		
		return jmp[u][0];
	};
	
	int ans = 1e9;
	
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			int p = lca(i, j);
			
			if(sd[i] + sd[j] - 2 * sd[p] == k) {
				ans = min(ans, d[i] + d[j] - 2 * d[p]);
			}
		}
	}
	
	if(ans == 1e9) ans = -1;
	
	return ans;
}

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