Submission #555536

#	Time	Username	Problem	Language	Result	Execution time	Memory
555536		xdfactor2034	Race (IOI11_race)	C++17	21 / 100	3048 ms	29820 KiB

race

#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int mxN = 2e5+5;
using pii = pair<int,int>;
vector<pii> tr[mxN];
int N, K, res = LLONG_MAX, tin[mxN],tout[mxN], jump[mxN][19], lr[mxN], dr[mxN], dep, di, timer;
bool anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
void dfs(int x, int p) {
	dep++;
	lr[x] = dep, dr[x] = di, tin[x] = ++timer, jump[x][0] = p;
	for(int i = 1; i <= 18; i++) jump[x][i] = jump[jump[x][i-1]][i-1];
	for(auto it : tr[x]) if(it.second != p) {
		di += it.first;
		dfs(it.second,x);
		di -= it.first;
	}
	dep--, tout[x] = ++timer;
}
int lca(int u, int v) {
	if(anc(u,v))return u;
	if(anc(v,u))return v;
	for(int i = 18; i >= 0; i--) if(!anc(jump[u][i],v)) u = jump[u][i];
	return jump[u][0];
}
int len(int u, int v) {
	return lr[u]+lr[v]-2*lr[lca(u,v)];
}
int dist(int u, int v) { return dr[u]+dr[v]-2*dr[lca(u,v)]; }

signed best_path(signed n, signed k, signed h[][2], signed l[]) {
	N = n, K = k;
	for(int i = 0; i < N-1; i++) {
		int a = h[i][0], b = h[i][1], w = l[i];
		tr[a].push_back({w,b});
		tr[b].push_back({w,a});
	}
	dfs(0,0);
	int res = LLONG_MAX;
	for(int i = 0; i < N; i++) {
		for(int j = i+1; j < N; j++) {
			if(dist(i,j) == K) res = min(res, len(i,j));
		}
	}
	if(res == LLONG_MAX) return -1; else return res;
}

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