Submission #1112940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112940		akzytr	Race (IOI11_race)	C++17	43 / 100	3065 ms	106484 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ve vector
#define pb push_back
#define ar array
#define ll long long
using namespace std;

const int MAXN = 3e5;
set<int> adj[MAXN];
map<ar<int, 2>, int> w;

int K;
int ANS = 1e9;

int sub[MAXN];
int processed[MAXN];

void find_size(int x, int p) {
	sub[x] = 1;
	for(int i : adj[x]) {
		if(i != p && !processed[i]) {
			find_size(i, x);
			sub[x] += sub[i];
		}
	}
}
int find_centroid(int x, int p, int n) {
	for(int i : adj[x]) {
		if(sub[i] > n / 2 && i != p) {
			return find_centroid(i, x, n);
		}
	}
	return x;
}

void dfs(int x, int p, map<int, int> &vis, map<int, int> &mi_edge, int we, int num_edge, bool upd) {
	if(upd) {
		if(vis[we]) {
			mi_edge[we] = min(mi_edge[we], num_edge);
		} else {
			vis[we] = 1;
			mi_edge[we] = num_edge;
		}
	} else {
		if(vis[K - we]) {
			ANS = min(ANS, num_edge + mi_edge[K - we]);
		}
	}

	for(int i : adj[x]) {
		if(i != p && we + w[{i, x}] <= K && !processed[i]) {
			dfs(i, x, vis, mi_edge, we + w[{i, x}], num_edge + 1, upd);
		}
	}
}
void process_centroid(int x) {
	map<int, int> vis;
	map<int, int> mi_edge;
	mi_edge[0] = 0;
	vis[0] = 1;

	for(int i : adj[x]) {
		dfs(i, x, vis, mi_edge, w[{i, x}], 1, false);
		dfs(i, x, vis, mi_edge, w[{i, x}], 1, true);
	}
	processed[x] = 1;
}

void decompo(int x) {
	find_size(x, -1);
	int centroid = find_centroid(x, -1, sub[x]);
	process_centroid(centroid);

	for(int i : adj[centroid]) {
		adj[i].erase(centroid);
		decompo(i);
	}
}

int best_path(int N, int Ked, int H[][2], int L[]) {
	fill(processed, processed + MAXN, 0);
	for(int i = 0; i < N - 1; i++) {
		int a, b;
		a = H[i][0];
		b = H[i][1];

		adj[a].insert(b);
		adj[b].insert(a);
		w[{a, b}] = L[i];
		w[{b, a}] = L[i];
	}
	K = Ked;
	decompo(0);
	if(ANS != 1e9) {
		return ANS;
	}
	return -1;
}

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