Submission #927945

#	Time	Username	Problem	Language	Result	Execution time	Memory
927945		TAhmed33	Race (IOI11_race)	C++98	100 / 100	751 ms	45336 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 2e5 + 24;
int sze[MAX];
bitset <MAX> vis;
int k;
vector <pair <int, int>> adj[MAX];

void calc (int pos, int par) {
	sze[pos] = 1;
	for (auto j : adj[pos]) {
		if (j.first == par || vis[j.first]) continue;
		calc(j.first, pos);
		sze[pos] += sze[j.first];		
	}
}

int find (int pos, int par, int kk) {
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		if (vis[j.first]) continue;
		if (sze[j.first] > (kk >> 1)) return find(j.first, pos, kk);
	}
	return pos;
}

int mn = 1e10;
map <int, int> cnt;

void ll2 (int pos, int par, int dep, int dist) {
	if (dist > k) return;
	if (cnt.count(k - dist)) mn = min(cnt[k - dist] + dep, mn);
	for (auto j : adj[pos]) {
		if (j.first != par && !vis[j.first]) {
			ll2(j.first, pos, dep + 1, dist + j.second);
		}
	}	
}

void ll (int pos, int par, int dep, int dist) {
	if (dist > k) return;
	if (cnt.count(dist)) cnt[dist] = min(cnt[dist], dep);
	else cnt[dist] = dep;
	for (auto j : adj[pos]) {
		if (j.first != par && !vis[j.first]) {
			ll(j.first, pos, dep + 1, dist + j.second);
		}
	}
}

void decomp (int pos) {
	calc(pos, -1);
	int c = find(pos, -1, sze[pos]);
	vis[c] = 1;
	cnt[0] = 0;
	for (auto j : adj[c]) {
		if (vis[j.first]) continue;
		ll2(j.first, c, 1, j.second);	
		ll(j.first, c, 1, j.second);
	}
	cnt.clear();
	for (auto i : adj[c]) {
		if (!vis[i.first]) {
			decomp(i.first);
		}
	}
}

int32_t best_path (int32_t n, int32_t K, int32_t h[][2], int32_t l[]) {
	k = K;
	for (int i = 0; i + 1 < n; i++) {
		adj[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
		adj[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
	}
	for (int i = 1; i <= n; i++) {
		vis[i] = 0;
	}
	decomp(1);
	return (mn >= 1e10 ? -1 : mn);
}

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