Submission #653026

#	Time	Username	Problem	Language	Result	Execution time	Memory
653026		beaconmc	Race (IOI11_race)	C++14	100 / 100	1049 ms	64912 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;


bool r[300000];
vector<vector<ll>> edges[300000];

ll sub[300000];
ll n,m,root,k;
vector<vector<ll>> twosum;
ll ans = 1000000000;

ll dfs(ll a, ll p){

	sub[a] = 1;
	for (auto& i : edges[a]){
		if (i[0]!=p && !r[i[0]]) sub[a] += dfs(i[0], a);
	}
	return sub[a];
}

void dfs2(ll a, ll p, ll v, ll num, ll col){
	for (auto& i : edges[a]){
		if (i[0]!=p && !r[i[0]]) dfs2(i[0], a, v+i[1], num+1, col);
	}
	twosum.push_back({v, num, col});
}



ll centroid(ll a, ll sz, ll p){

	for (auto&i : edges[a]){
		if (i[0]!=p && !r[i[0]] && sub[i[0]]*2 > sz){
			return centroid(i[0], sz, a);
		}
	}
	return a;
}

void decomp(ll a, ll p){
	ll c = centroid(a, dfs(a, -1), -1);

	twosum.clear();

	ll col = 0;
	for (auto&i : edges[c]){
		if (!r[i[0]]) dfs2(i[0], c, i[1],1,col);
		twosum.push_back({0,0,col});
		col++;
	}


	sort(twosum.begin(), twosum.end());
	ll lo = 0;
	ll hi = twosum.size()-1;

	while (lo<=hi){
		if (twosum[lo][0] + twosum[hi][0] > k){
			hi--;
		}else if (twosum[lo][0] + twosum[hi][0] == k){
			if (twosum[lo][2] == twosum[hi][2]){
				if (twosum[hi][0] != twosum[hi-1][0]){
					lo++;
					continue;
				}
				hi--;
				continue;
			}else{
				ans = min(ans, twosum[lo][1] + twosum[hi][1]);
				hi --;
			}
		}else if (twosum[lo][0] + twosum[hi][0] < k){
			lo++;
		}
	}


	r[c] = 1;
	for (auto&i : edges[c]){
		if (!r[i[0]]) decomp(i[0], c);
	}
}




int best_path(int N, int K, int H[][2], int L[])
{
	n = N;
	k = K;
	FOR(i,0,n-1){
		ll a,b,c;
		a = H[i][0];
		b = H[i][1];
		c = L[i];
		edges[a].push_back({b,c});
		edges[b].push_back({a,c});
	}
	decomp(0,-1);
	if (ans == 1000000000) ans = -1;
	return ans;
}

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