Submission #848976

#	Time	Username	Problem	Language	Result	Execution time	Memory
848976		ilhan_arda	Race (IOI11_race)	C++17	0 / 100	1 ms	2396 KiB

race

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
//~ #define int long long
using namespace std;
typedef long long ll;
typedef tuple<int, int, int> iii;

const int inf = 1000000000;
int rem, ans=inf, k, centroid;
vector<vector<pair<int, int>>> graph;
vector<int> sub;
map<int, int> sums, tempsums;

vector<bool> vis, mark;
int dfs1(int node, int par){
	int val= 1;
	mark[node]=true;
	for(auto it: graph[node]){
		if(it.fi==par)continue;
		if(vis[it.fi])continue;
		val+=dfs1(it.fi, node);
	}
	sub[node]=val;
	return val;
}
void dfs2(int node, int par, int cur, int len){
	if(cur>k)return;
	if(k==cur){
		ans=min(ans, len);
	}
	else if(sums[k-cur]){
		ans=min(ans, sums[k-cur]+len);
	}
	for(auto it: graph[node]){
		if(vis[it.fi])continue;
		if(it.fi==par)continue;
		if(node==centroid){
			for(auto it: tempsums){
				if(!sums[it.fi])sums[it.fi]=it.se;
				sums[it.fi]=min(it.se, sums[it.fi]);
			}
			tempsums.clear();
		}
		dfs2(it.fi, node, cur+it.se, len+1);
	}
	if(!tempsums[cur])tempsums[cur]=len;
	tempsums[cur]=min(len, sums[cur]);
	return;
}
int findcentroid(int node, int par, int sz){
	for(auto it: graph[node]){
		if(vis[it.fi])continue;
		if(it.fi==par)continue;
		if(sub[it.fi]>=sz/2){
			return findcentroid(it.fi, node, sz);
		}
	}
	return node;
}
int best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
	rem = N;
	k=K;
	graph.assign(N+5, vector<pair<int, int>>());
	vis.assign(N+5, false);
	for(int i=0;i<N-1;i++){
		graph[H[i][1]].pb({H[i][0], L[i]});
		graph[H[i][0]].pb({H[i][1], L[i]});
	}
	while(rem){
		mark.assign(N+5, false);
		sub.assign(N+5, 0);
		for(int i=0;i<N;i++){
			sums.clear();
			tempsums.clear();
			if(mark[i] || vis[i])continue;
			int sz=dfs1(i, -1);
			centroid=findcentroid(i, -1, sz);
			dfs2(centroid, -1, 0, 0);
			vis[centroid]=true;
			rem--;
		}
	}
	if(ans==inf)return -1;
	return ans;
}

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