Submission #804954

#	Time	Username	Problem	Language	Result	Execution time	Memory
804954		Gangsta	Race (IOI11_race)	C++14	0 / 100	4 ms	4948 KiB

race

// a >> b = a / pow(2,b)
// a << b = a * pow(2,b)
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define sz size()
#define ss second
#define ff first
#define N 200001
#define LOG 20
#define pii pair<int,int>

using namespace std;

int n, m, u[N], v[N], w[N], par[N], lvl[N], P[N][LOG];

ll p[N][LOG];

vector<pii> adj[N];

void dfs(int nd, int pr){
	for(auto i : adj[nd]){
		if(i.ff == pr) continue;
		P[i.ff][0] = nd;
		p[i.ff][0] = i.ss;
		lvl[i.ff] = lvl[nd] + 1;
		dfs(i.ff,nd);
	}
}

pii olala(int nd, int k){
	ll sum = 0;
	for(int i = LOG - 1; i >= 0; i--){
		if(k >> i&1){
			sum += p[nd][i];
			nd = P[nd][i];
		}
	}
	return {nd,sum};
}

int LCA(int a, int b){
	if(lvl[a] < lvl[b]) b = olala(b,lvl[b] - lvl[a]).ff;
	else if(lvl[a] > lvl[b]) a = olala(a,lvl[a] - lvl[b]).ff;
	if(a == b) return a;
	for(int i = LOG - 1; i >= 0; i--){
		if(P[a][i] != P[b][i]){
			a = P[a][i];
			b = P[b][i];
		}
	}
	return P[a][0];
}

int best_path(int n, int k, int h[N][2], int l[N]){
	int mn = N;
	for(int i = 1; i < n; i++){
		adj[h[i][0]].pb({h[i][1],l[i]});
		adj[h[i][1]].pb({h[i][0],l[i]});
	}
	dfs(0,-1);
	for(int i = 1; i < LOG; i++){
		for(int j = 1; j <= n; j++){
			if(P[j][i-1]){
				P[j][i] = P[P[j][i-1]][i-1];
				p[j][i] = p[j][i-1] + p[P[j][i-1]][i-1];
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			int c = LCA(i,j);
			ll jogap = olala(i,lvl[i] - lvl[c]).ss + olala(j,lvl[j] - lvl[c]).ss;
			if(jogap == k) mn = min(mn,lvl[i] + lvl[j] - 2*lvl[c]);
		}
	}
	if(mn == N) return -1;
	else return mn;
}

//int main(){
//	int n, k, h[N][2];
//	ll l[N];
//	cin >> n >> k;
//	for(int i = 1; i < n; i++){
//		cin >> h[i][0] >> h[i][1];
//	}
//	for(int i = 1; i < n; i++){
//		cin >> l[i];
//	}
//	cout << best_path(n,k,h,l);
//}

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