Submission #1145378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145378		sano	Race (IOI11_race)	C++20	100 / 100	638 ms	44836 KiB

race

#include "race.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 1000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

vec<vec<pii>> g;
vec<int> pod;
int n, k;
vec<bool> je;
int pods(int x, int pr = -1) {
	pod[x] = 1;
	for(auto&i : g[x]) {
		if (i.ff == pr) continue;
		if (je[i.ff]) continue;
		pod[x] += pods(i.ff, x);
	}
	return pod[x];
}

int centroid(int x, int vel, int pr = -1) {
	for (auto i : g[x]) {
		if (i.ff == pr) continue;
		if (je[i.ff]) continue;
		if (pod[i.ff] * 2 > vel) return centroid(i.ff, vel, x);
	}
	return x;
}

int mini = -1;

void dfs(int x, vec<pii>& h, int pr, int d, int dh) {
	h.push_back({ d, dh });
	for (auto&i : g[x]) {
		if (i.ff == pr) continue;
		if (je[i.ff]) continue;
		dfs(i.ff, h, x, d + i.ss, dh + 1);
	}
	return;
}

void ries(int x) {
	pods(x);
	int c = centroid(x, pod[x]);
	unordered_map<int, int> umap;
	umap[0] = 0;
	for (auto i : g[c]) {
		if (je[i.ff]) continue;
		vec<pii> h;
		dfs(i.ff, h, c, i.ss, 1);
		for (auto j : h) {
			if (umap.find(k - j.ff) != umap.end()) {
				mini = min(mini, umap[k - j.ff] + j.ss);
			}
		}
		for (auto j : h) {
			if (umap.find(j.ff) == umap.end()) {
				umap[j.ff] = j.ss;
			}
			umap[j.ff] = min(umap[j.ff], j.ss);
		}
	}
	je[c] = 1;
	for (auto i : g[c]) {
		if (je[i.ff]) continue;
		ries(i.ff);
	}
}

int best_path(int n1, int k1, int h[][2], int l[]) {
	n = n1; k = k1;
	mini = n + 1;
	g.resize(n);
	pod.resize(n);
	je.resize(n, false);
	For(i, n-1) {
		g[h[i][0]].push_back({ h[i][1], l[i] });
		g[h[i][1]].push_back({ h[i][0], l[i] });
	}
	ries(0);
	if (mini == (n + 1)) mini = -1;
	return mini;
}

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