Submission #513849

#	Time	Username	Problem	Language	Result	Execution time	Memory
513849		Eyed	Race (IOI11_race)	C++17	0 / 100	7 ms	14412 KiB

race

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;

//IOI 2011 Race
// Problem: https://oj.uz/problem/view/IOI11_race

struct edge {
	int b;
	int w;
	edge(int a = 0, int y = 0) : b(a), w(y) {};
};

int n;
int k;
vector<edge> tree[200005];
map<int, int> dists[200005];
int minK[200005];

void dfs(int x, int p) {
	dists[x][0] = 0;
	minK[x] = 1e9;
	for (edge e : tree[x]) {
		int v = e.b;
		int c = e.w;
		if (v == p) continue;
		dfs(v, x);
		if (dists[v].size() > dists[x].size()) dists[x].swap(dists[v]);
		minK[x] = min(minK[x], minK[v]);
		for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
			int d = itr->first;
			int ns = itr->second;
			if (dists[x].find(k - d - c) != dists[x].end()) {
				minK[x] = min(minK[x], ns + 1 + dists[x][k - d - c]);
			}
		}
		for (auto itr = dists[v].begin(); itr != dists[v].end(); ++itr) {
			int d = itr->first;
			int ns = itr->second;
			if (dists[x].find(d + c) != dists[x].end()) dists[x][d + c] = min(dists[x][d + c], ns + 1);
			else dists[x][d + c] = ns + 1;
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	k = K;
	for (int i = 0; i < n - 1; ++i) {
		tree[H[i][0]].push_back(edge(H[i][1], L[i]));
		tree[H[i][1]].push_back(edge(H[i][0], L[i]));
	}
	dfs(0, 0);
	if (minK[0] != 1e9) return minK[0];
	return -1;
}

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