Submission #361357

#	Time	Username	Problem	Language	Result	Execution time	Memory
361357		ronnith	Race (IOI11_race)	C++14	0 / 100	6 ms	9728 KiB

race

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

using namespace std;
using ll = long long;

#define f first
#define s second

const int NN = 200000;
const int MX = 1000000;

int n, k, sz[NN];
ll level[NN];
map<ll, ll> min_edges;
ll ANS = INT_MAX, dist[NN];
vector<int> nodes[NN];
vector<pair<int, int>> adj[NN];

void dfs_pre(int x, int pr, int lvl, ll sm) {
	sz[x] = 1, level[x] = lvl, dist[x] = sm;
	for(auto e : adj[x]) if(e.f != pr) {
		dfs_pre(e.f, x, lvl + 1, sm + e.s);
		sz[x] += sz[e.f];
	}
}

void dfs(int x, int pr, bool keep) {
	int mx = 0, big_child = -1;
	for(auto e : adj[x]) {
		if(e.f != pr) {
			if(sz[e.f] > mx) {
				mx = sz[e.f];
				big_child = e.f;
			}
		}
	}
	if(big_child == -1) {
		nodes[x].push_back(x);
		if(keep) {
			min_edges[dist[x]] = level[x];
		}
		return;
	}
	for(auto e : adj[x]) {
		if(e.f != pr && e.f != big_child) {
			dfs(e.f, x, false);
		}
	}
	dfs(big_child, x, true);
	swap(nodes[x], nodes[big_child]);
	nodes[x].push_back(x);
	if(min_edges.find(dist[x]) == min_edges.end()) {
		min_edges[dist[x]] = level[x];
	} else {
		min_edges[dist[x]] = min(min_edges[dist[x]], level[x]);
	}
	if(min_edges.find(dist[x] + k) != min_edges.end()) {
		ANS = min(ANS, min_edges[dist[x] + k]);
	}
	for(auto e : adj[x]) {
		if(e.f != pr && e.f != big_child) {
			for(auto nd : nodes[e.f]) {
				ll d = dist[nd] - dist[x];
				int lvl = level[nd] - level[x];
				if(d == k) {
					ANS = min(ANS, ll(lvl));
				} else if(d < k && min_edges.find(k - d + dist[x]) != min_edges.end()){
					ANS = min(ANS, min_edges[k - d + dist[x]] - level[x] + lvl);
				}
				nodes[x].push_back(nd);
				if(min_edges.find(dist[nd]) == min_edges.end()) {
					min_edges[dist[nd]] = level[nd];
				} else {
					min_edges[dist[nd]] = min(min_edges[dist[x]], level[nd]);
				}
			}
		}
	}
	if(!keep) {
		for(auto& e : min_edges) {
			e.s = INT_MAX;
		}
	}
}

int solve() {
	dfs_pre(0, -1, 0, 0);
	dfs(0, -1, true);
	return (ANS == INT_MAX ? -1 : ANS);
}

int best_path(int _N, int K, int H[][2], int L[]) {
	n = _N, k = K;
	for(int i = 0;i < n - 1;i ++) {
		adj[H[i][0]].emplace_back(H[i][1], L[i]);
		adj[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	return solve();
}

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