Submission #668532

#	Time	Username	Problem	Language	Result	Execution time	Memory
668532		chanhchuong123	Race (IOI11_race)	C++14	31 / 100	431 ms	57984 KiB

race

#include <bits/stdc++.h>
#include <race.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  	if (a < b) {a = b; return true;} return false;
}

const int N = 2e5 + 3;
int n, k;
long long h[N];
vector<pair<int, int>> adj[N];

int sz[N], heavy[N], dep[N];
void pre_dfs(int u, int p) {
	sz[u] = 1; heavy[u] = -1;
	for (pair<int, int> &x: adj[u]) if (x.fi != p) {
		int v = x.fi, w = x.se;
		dep[v] = dep[u] + 1;
		h[v] = h[u] + w;
		pre_dfs(v, u);
		sz[u] += sz[v];
		if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
	}
}

int LCA, ans = N;
vector<pair<long long, int>> store;
map<pair<long long, int>, int> cnt;

void update(int u, int p, int delta) {
	if (delta == +1) {
		pair<long long, int> need(k + 2 * h[LCA] - h[u], -1);
		store.push_back({h[u], dep[u]});
		auto it = cnt.lower_bound(need);
		if (it != cnt.end() && (*it).fi.fi == need.fi) 
			mini(ans, dep[u] + (*it).fi.se - 2 * dep[LCA]);
	} else {
		cnt[{h[u], dep[u]}]--; 
		if (!cnt[{h[u], dep[u]}]) cnt.erase({h[u], dep[u]});
	}
	for (pair<int, int> &x: adj[u]) if (x.fi != p) update(x.fi, u, delta);

}

void dfs(int u, int p) {
	for (pair<int, int> &x: adj[u]) if (x.fi != p && x.fi != heavy[u]) {
		dfs(x.fi, u); update(x.fi, u, -1);
	}
	if (heavy[u] != -1) {
		dfs(heavy[u], u); LCA = u;
		for (pair<int, int> &x: adj[u]) if (x.fi != p && x.fi != heavy[u]) update(x.fi, u, +1);
		while (store.size()) {
			cnt[store.back()]++;
			store.pop_back();
		}
	}
	auto it = cnt.lower_bound({h[u] + k, -1}); 
	if (it != cnt.end() && (*it).fi.fi == h[u] + k) 
		mini(ans, (*it).fi.se - dep[u]);
	cnt[{h[u], dep[u]}]++;
}

int best_path(int _n, int _k, int H[][2], int L[]) {
	n = _n; k = _k;
	for (int i = 0; i < n - 1; i++) {
		int u = H[i][0], v = H[i][1], w = L[i];
		adj[u].push_back({v, w});
  		adj[v].push_back({u, w});
	}
	pre_dfs(0, -1); dfs(0, -1);
  	return (ans == N ? -1 : ans);
}

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