Submission #990503

#	Time	Username	Problem	Language	Result	Execution time	Memory
990503		mateuszwes	Race (IOI11_race)	C++17	0 / 100	2 ms	12888 KiB

race

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
#define ull unsigned ll

#include "race.h"

using namespace std;

constexpr int debug = 1;
constexpr int M = 2e5+7;
constexpr int D = 1e6+7;

int tree_size[M];
int total_size;
bool was_centroid[M];
ll Kek;
ll mini = 1e9+7;
ll closest[D];
queue<int> changes; 		//komorki z closest do wyzerowania

vector<pair<ll,ll>> adj[M];

inline void addEdge(ll a, ll b, ll val){
	adj[a].pb({b, val});
	adj[b].pb({a, val});
}

void set_size(int s, int p){
	tree_size[s] = 1;
	for(auto k: adj[s]){
		if(k.F == p || was_centroid[k.F]) continue;
		set_size(k.F, s);
		tree_size[s] += tree_size[k.F];
	}
}

int find_centroid(int s, int p){
	for(auto k: adj[s]){
		if(was_centroid[k.F]) continue;
		else if(k.F == p){
			if(total_size-tree_size[s] > total_size/2) return find_centroid(k.F, s);
		}
		else if(tree_size[k.F] > total_size/2){
			return find_centroid(k.F, s);
		}
	}
	return s;
}

void DFS1(int s, int p, ll dist_v, ll dist_e){		//sprawdza, ile ma odpowiadajacy wierzcholek
	if(dist_e == Kek) mini = min(mini, dist_v+1);
	if((dist_e < Kek) && (closest[Kek-dist_e])) mini = min(mini, closest[Kek-dist_e]+dist_v);

	for(auto k: adj[s]){
		if(was_centroid[s] || k.F == p) continue;
		DFS1(k.F, s, dist_v+1, dist_e+k.S);
	}
}

void DFS2(int s, int p, ll dist_v, ll dist_e){	//aktualizacje wierzcholkow w danych odleglosciach
	if(dist_e <= Kek && dist_e != 0){
		if(closest[dist_e] == 0 || closest[dist_e] > dist_v){
			changes.push(dist_e);
			closest[dist_e] = dist_v;
		}
	}
	
	for(auto k: adj[s]){
		if(was_centroid[s] || k.F == p) continue;
		DFS2(k.F, s, dist_v+1, dist_e+k.S);
	}
}

void centroid_decomposition(int x){
	set_size(x, x);
	total_size = tree_size[x];
	int cen = find_centroid(x, x);

	//robi cos na centroidzie

	for(auto k: adj[cen]){
		if(!was_centroid[k.F]){
			DFS1(k.F, cen, 1, k.S);
			DFS2(k.F, cen, 1, k.S);
		}
	}

	while(!changes.empty()){
		closest[changes.front()] = 0;
		changes.pop();
	}

	was_centroid[cen] = 1;

	for(auto k: adj[cen]){
		if(!was_centroid[k.F]) centroid_decomposition(k.F);
	}
	
}

int best_path(int N, int K, int H[][2], int L[]){
  	Kek = K;

  	for(int i = 0; i < N-1; i++){
  		addEdge(H[i][0], H[i][1], L[i]);
  	}

  	centroid_decomposition(0);
  	if(mini == 1e9+7) mini = -1;

  	return mini;
}

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