제출 #1288293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288293		muhammad-ahmad	Race (IOI11_race)	C++20	0 / 100	5 ms	9784 KiB

race

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

using namespace std;

const int N  = 2e5 + 5;

int n, k, ans = 1e9;
int depth[N], dist[N];
vector<pair<int, int>> adj[N];
set<pair<int, int>> S[N];

void dfs(int u = 1, int p = 0){
	for (auto [v, w]: adj[u]){
		if (v == p) continue;
		dist[v] = dist[u] + w;
		depth[v] = depth[u] + 1;
		dfs(v, u);
	}
}

void STL(int u = 1, int p = 0){
	for (auto [v, w] : adj[u]){
		if (v != p) STL(v, u);	
	}
	
	if (u != 1 && adj[u].size() == 1){
		S[u].insert({dist[u], depth[u]});
		return;
	}
	
	int i = 0;
	for (auto [v, w] : adj[u]){
		if (v != p && S[v].size() > S[i].size()) i = v;
	}
	
	swap(S[i], S[u]);
	
	int line = dist[u] + k, bend = k + dist[u] * 2;
	auto it = S[u].lower_bound({line, 0});
	if (it != S[u].end()){
		pair<int, int> pos = *it;
		if (pos.first == line)
			ans = min(ans, pos.second - depth[u]);
	}
	
	for (auto [v, w] : adj[u]){
		if (v == i or v == p) continue;
		for (auto [Dis, Dep] : S[v]){
			if (Dis == line) ans = min(ans, Dep - depth[u]);
			auto it = S[u].lower_bound({bend - Dis, 0});
			if (it != S[u].end()){
				pair<int, int> pos = *it;
				if (pos.first == bend - Dis)
					ans = min(ans, pos.second + Dep - 2 * depth[u]);
			}
		}
		
		for (auto i : S[v]) S[u].insert(i);
	}

}

int best_path(int NNN, int KKK, int ADJ[][2], int W[]){
	n = NNN, k = KKK;
	for (int i = 0; i < n - 1; i++){
		int u = ADJ[i][0] + 1, v = ADJ[i][1] + 1, w = W[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	dfs();
	STL();
	return ans;
}

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