Submission #832020

#	Time	Username	Problem	Language	Result	Execution time	Memory
832020		serifefedartar	Race (IOI11_race)	C++17	100 / 100	1029 ms	46332 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 1000005

vector<vector<pair<int,int>>> graph;
vector<int> sz, marked;
map<int,int> mp;
int req_len;
int ans = 1e8;
int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			sz[node] += get_sz(u.f, node);
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f] && sz[u.f] * 2 >= n)
			return find_centro(u.f, node, n);
	}
	return node;
}

void eval(int node, int parent, int dist, int edges) {
	if (dist > req_len)
		return ;
	if (req_len-dist == 0)
		ans = min(ans, edges);
	else if (req_len-dist != 0 && mp[req_len-dist] != 0)
		ans = min(ans, mp[req_len - dist] + edges);
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			eval(u.f, node, dist + u.s, edges + 1);
	}
}

void add(int node, int parent, int dist, int edges) {
	if (dist > req_len)
		return ;
	if (mp[dist] == 0)
		mp[dist] = edges;
	else
		mp[dist] = min(mp[dist], edges);
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			add(u.f, node, dist + u.s, edges + 1);
	}
}

void solve(int node, int parent) {
	int n = get_sz(node, parent);
	int centro = find_centro(node, parent, n);

	marked[centro] = true;
	mp = map<int,int>();
	for (auto u : graph[centro]) {
		if (!marked[u.f]) {
			eval(u.f, centro, u.s, 1);
			add(u.f, centro, u.s, 1);
		}
	}

	for (auto u : graph[centro]) {
		if (u.f != parent && !marked[u.f])
			solve(u.f, centro);
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	req_len = K;
	graph = vector<vector<pair<int,int>>>(N, vector<pair<int,int>>());
	sz = vector<int>(N);
	marked = vector<int>(N, false);
	for (int i = 0; i < N-1; i++) {
		graph[H[i][0]].push_back({H[i][1], L[i]});
		graph[H[i][1]].push_back({H[i][0], L[i]});
	}
	solve(0, 0);

	if (ans >= 1e8)
		return -1;
	else
		return ans;
}

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