Submission #718079

#	Time	Username	Problem	Language	Result	Execution time	Memory
718079		andrei_c1	Race (IOI11_race)	C++14	0 / 100	1 ms	304 KiB

race

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

using namespace std;

const int INF = 1e9;

int k;
vector<int> sz;
vector<bool> rem;
vector<vector<pair<int, int>>> adj;

void minSelf(int &x, int y) {
	if(y < x) {
		x = y;
	}
}

void dfs(int u, int v = -1) {
	sz[u] = 1;
	for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
		dfs(it.first, u);
		sz[u] += sz[it.first];
	}
}

int centroid(int desired, int u, int v = -1) {
	for(const auto &it: adj[u]) if(it.first != v && !rem[it.first] && (sz[it.first] << 1) > desired) {
		return centroid(desired, it.first, u);
	}
	return u;
}

map<int, int> mp;

void dfsUpdate(int u, int v, int dep, int cnt = 1) {
	if(k >= dep) {
		if(dep != 0 && mp.count(dep) == 0) {
			mp.emplace(dep, cnt);
		} else {
			minSelf(mp[dep], cnt);
		}
		for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
			dfsUpdate(it.first, u, dep + it.second, cnt + 1);
		}
	}
}

int dfsQuery(int u, int v, int dep, int cnt = 1) {
	int ans = INF;
	if(k >= dep) {
		if(mp.count(k - dep) > 0) {
			minSelf(ans, cnt + mp[k - dep]);
		}
		for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
			minSelf(ans, dfsQuery(it.first, u, dep + it.second, cnt + 1));
		}
	}
	return ans;
}

void preorder(int u, int v, int dep, int cnt = 1) {
	for(const auto &it: adj[u]) if(it.first != v && !rem[it.first]) {
		preorder(it.first, u, dep + it.second, cnt + 1);
	}
}

int solve(int u = 0) {
	dfs(u);
	int c = centroid(sz[u], u);

	int ans = INF;
	for(const auto &it: adj[c]) if(!rem[it.first]) {
		minSelf(ans, dfsQuery(it.first, c, it.second));
		dfsUpdate(it.first, c, it.second);
	}
	if(mp.count(k) > 0) {
		minSelf(ans, mp[k]);
	}
	rem[c] = 1;
	mp.clear();

	for(const auto &it: adj[c]) if(!rem[it.first]) {
		minSelf(ans, solve(it.first));
	}
	return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
	adj = vector<vector<pair<int, int>>> (N);

	for(int i = 0; i < N; i++) {
		adj[H[i][0]].emplace_back(H[i][1], L[i]);
		adj[H[i][1]].emplace_back(H[i][0], L[i]);
	}

	sz = vector<int> (N);
	rem = vector<bool> (N);
	k = K;

	int ans = solve();
	if(ans == INF) {
		return -1;
	} else {
		return ans;
	}
}

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