Submission #643513

#	Time	Username	Problem	Language	Result	Execution time	Memory
643513		brobat	Race (IOI11_race)	C++17	100 / 100	715 ms	40148 KiB

race

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

int n, k;
vector <vector<pair<int, int>>> adj;
vector <bool> vis;
vector <int> sz;
int ans = 1E9;

void find_size(int node, int prev) {
	sz[node] = 1;
	for(auto [next, wt] : adj[node]) {
		if(next != prev && !vis[next]) {
			find_size(next, node);
			sz[node] += sz[next];
		}
	}
}

int centroid(int node, int prev, int n) {
	for(auto [next, wt] : adj[node]) {
		if(next != prev && !vis[next] && sz[next] > n/2) {
			return centroid(next, node, n);
		}
	}
	return node;
}

void dfs(int node, int prev, int weight, int depth, vector <pair<int, int>> &store) {
	store.push_back({weight, depth});
	for(auto [next, wt] : adj[node]) {
		if(next != prev && !vis[next]) {
			dfs(next, node, min(weight + wt, (int)1E9), depth + 1, store);
		}
	}
}

void process(int node) {
	vector<vector<pair<int, int>>> paths; // {sum of weights, length}.
	for(auto [next, wt] : adj[node]) {
		if(!vis[next]) {
			vector <pair<int, int>> temp;
			dfs(next, node, wt, 1, temp);
			paths.push_back(temp);
		}
	}
	// cout << node << '\n';
	// for(auto i : paths) {
		// for(auto j : i) cout << "{" << j.first << "," << j.second << "} ";
		// cout << '\n';
	// }
	if(paths.empty()) return;
	set<pair<int, int>> s;
	for(auto i : paths[0]) {
		if(i.first == k) ans = min(ans, i.second);
		else if(i.first < k) s.insert(i);
	}
	for(int i = 1; i < (int)paths.size(); i++) {
		for(auto j : paths[i]) {
			if(j.first < k) {
				auto it = s.lower_bound({k - j.first, 0});
				if(it != s.end() && (*it).first == k - j.first) {
					ans = min(ans, j.second + (*it).second);
				}
			}
		}
		for(auto j : paths[i]) {
			if(j.first == k) ans = min(ans, j.second);
			else if(j.first < k) s.insert(j);
		}
	}
}

void solve(int node, int prev) {
	find_size(node, prev);
	int c = centroid(node, prev, sz[node]);
	process(c);
	vis[c] = true;
	for(auto [next, wt] : adj[c]) {
		if(!vis[next]) solve(next, c);
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	k = K;
	adj.clear(); adj.resize(n);
	vis.clear(); vis.resize(n, false);
	sz.clear(); sz.resize(n);
	ans = 1E9;
	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]});
	}
	solve(0, 0);
	if(ans > n) return -1;
	return ans;
}

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

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