Submission #1156930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156930		crispxx	Race (IOI11_race)	C++20	100 / 100	663 ms	43280 KiB

race

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

using namespace std;

// #include "grader.cpp"

#define all(x) x.begin(), x.end()

const int mxN = 2e5 + 5;

vector<pair<int, int>> adj[mxN];
map<long long, int> mp;
int sbz[mxN], del[mxN];

int k;

int ans = 1e9;

void dfs(int v, int p) {
	sbz[v] = 1;
	for(auto [to, w] : adj[v]) {
		if(to == p || del[to]) continue;
		dfs(to, v);
		sbz[v] += sbz[to];
	}
}

int Centroid(int v, int p, int size) {
	for(auto [to, w] : adj[v]) {
		if(to == p || del[to]) continue;
		if(sbz[to] * 2 > size) {
			return Centroid(to, v, size);
		}
	}
	return v;
}

void Ans(int v, int p, int d, long long cost) {
	if(mp.count(k - cost)) {
		ans = min(ans, d + mp[k - cost]);
	}
	for(auto [to, w] : adj[v]) {
		if(to == p || del[to]) continue;
		Ans(to, v, d + 1, cost + w);
	}
}

void Cnt(int v, int p, int d, long long cost) {
	if(mp.count(cost)) {
		mp[cost] = min(mp[cost], d);
	} else mp[cost] = d;
	for(auto [to, w] : adj[v]) {
		if(to == p || del[to]) continue;
		Cnt(to, v, d + 1, cost + w);
	}
}

void Decom(int v) {
	dfs(v, v);
	int C = Centroid(v, v, sbz[v]);
	
	mp.clear();
	
	mp[0] = 0;
	
	for(auto [to, w] : adj[C]) {
		if(del[to]) continue;
		Ans(to, C, 1, w);
		Cnt(to, C, 1, w);
	}
	
	del[C] = 1;
	
	for(auto [to, w] : adj[C]) {
		if(!del[to]) Decom(to);
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	k = K;
	for(int i = 0; i < N - 1; i++) {
		auto [u, v] = H[i];
		adj[u].emplace_back(v, L[i]);
		adj[v].emplace_back(u, L[i]);
	}
	
	Decom(0);
	
	return (ans == 1e9 ? -1 : ans);
}

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