Submission #160923

#	Time	Username	Problem	Language	Result	Execution time	Memory
160923		Juney	Race (IOI11_race)	C++14	0 / 100	10 ms	9720 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) ((x).begin(), (x).end())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5 + 5;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int N, sz[MAXN], dep[MAXN], anc[MAXN][20], ans, K;
ll len[MAXN];
vector<pll> G[MAXN];
vector<int> CT[MAXN];
bool del[MAXN];
map<int, int> mp;

void init(int cur, int par) {
	dep[cur] = dep[par] + 1;
	anc[cur][0] = par;
	for(auto i : G[cur]) if(i.fi != par) {
		len[i.fi] = len[cur] + i.se;
		init(i.fi, cur);
	}
}

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	for(int k=19; k>=0; k--) if(dep[anc[b][k]] >= dep[a]) b = anc[b][k];
	if(a == b) return a;
	for(int k=19; k>=0; k--) if(anc[a][k] != anc[b][k]) {
		a = anc[a][k];
		b = anc[b][k];
	}
	return anc[a][0];
}

ll dis(int a, int b) { return len[a] + len[b] - 2 * len[lca(a, b)]; }

int szdfs(int cur, int par) {
	sz[cur] = 1;
	for(auto i : G[cur]) if(!del[i.fi] && i.fi != par) sz[cur] += szdfs(i.fi, cur);
	return sz[cur];
}

int cdfs(int cur, int par, int cap) {
	for(auto i : G[cur]) if(!del[i.fi] && i.fi != par && sz[i.fi] > cap) return cdfs(i.fi, cur, cap);
	return cur;
}

int decompose(int root, int par) {
	int cap = szdfs(root, par);
	int cen = cdfs(root, par, cap / 2);
	CT[par].push_back(cen);
	del[cen] = 1;
	for(auto i : G[cen]) if(!del[i.fi]) decompose(i.fi, cen);
	return cen;
}

void dfs(int cur, int k, int cnt) {
	if(dis(k, cur) > K) return;
	if(K == dis(k, cur) || mp[K - dis(k, cur)]) ans = min(ans, mp[K - dis(k, cur)] + cnt);
	for(auto nxt : CT[cur]) dfs(nxt, k, cnt+1);
	if(mp[dis(k, cur)] == 0) mp[dis(k, cur)] = cnt;
	else mp[dis(k, cur)] = min(mp[dis(k, cur)], cnt);
}

void solve(int cur) {
	for(auto nxt : CT[cur]) dfs(nxt, cur, 1);
	mp.clear();
	for(auto nxt : CT[cur]) solve(nxt);
}

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 a = H[i][0]+1, b = H[i][1]+1, c = L[i];
		G[a].push_back(pll(b, c)); G[b].push_back(pll(a, c));
	}
	init(1, 0);
	int root = decompose(1, 0);
	for(int k=1; k<20; k++) for(int i=1; i<=N; i++) anc[i][k] = anc[anc[i][k-1]][k-1];
	ans = 1e9;
	solve(root);
	if(ans == 1e9) return -1;
	return ans;
}

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