Submission #495714

#	Time	Username	Problem	Language	Result	Execution time	Memory
495714		Pietra	Race (IOI11_race)	C++14	21 / 100	3087 ms	56444 KiB

race

#include<bits/stdc++.h>
using namespace std ; 
#include "race.h"

const int inf = 1e9 + 5 ; 
const int maxn = 2e6 + 5 ; 

int sz[maxn], mark[maxn], ans, n, k, f[maxn] ;
vector<pair<int,int>> grafo[maxn] ; 

void dfs(int v, int p){

	sz[v] = 1 ; 

	for(auto a : grafo[v]){
		if(a.first == p || mark[a.first]) continue ; 
		dfs(a.first, v) ; 
		sz[v] += sz[a.first] ; 
	}

}

int find_cent(int v, int p, int szz){

	for(auto a : grafo[v]){
		if(a.first == p || mark[a.first] || 2*sz[a.first] <= szz) continue ;
		find_cent(a.first, v, szz) ;  
	}

	return v ; 

}

void make_count(int type, int v, int p, int dist, int lvl){

	if(dist > k) return ; 

	if(type == -1) f[dist] = inf ; 

	else f[dist] = min(f[dist], lvl) ; 

	for(auto a : grafo[v]){
		if(a.first == p || mark[a.first]) continue ; 
		make_count(type, a.first, v, dist+a.second, lvl+1) ; 
	}

}

void add(int v, int p, int dist, int lvl){

	if(dist > k) return ; 

	ans = min(ans, f[k-dist] + lvl) ; 

	for(auto a : grafo[v]){
		if(a.first == p || mark[a.first]) continue ; 
		add(a.first, v, dist + a.second, lvl+1) ; 
	}

}

void make_graph(int v, int p){

	dfs(v, p) ; 

	int c = find_cent(v, p, sz[v]) ; 

	mark[c] = 1 ; 
	f[0] = 0 ; 

	for(auto a : grafo[c]){
		if(a.first == p || mark[a.first]) continue ; 
		add(a.first, c, a.second, 1) ; 
		make_count(0, a.first, c, a.second, 1) ; 
	}

	for(auto a : grafo[c]){
		if(a.first == p || mark[a.first]) continue ; 
		make_count(-1, a.first, c, a.second, 1) ; 
	}

	for(auto a : grafo[c]){
		if(a.first == p || mark[a.first]) continue ; 
		make_graph(a.first, c) ; 
	}

}

int best_path(int N, int K, int H[maxn][2], int L[maxn]) {
  
  for(int i = 0 ; i < N - 1 ; i++){
  	grafo[H[i][0]].push_back({H[i][1], L[i]}) ; grafo[H[i][1]].push_back({H[i][0], L[i]}) ; 
  }

  k = K ; 

  for(int i = 1 ; i <= K ; i++) f[i] = inf ; 
  ans = inf ; 
  make_graph(0, -1) ; 
  
  return (ans == inf ? -1 : ans) ; 

}

// int32_t main(){

// 	ans = inf ; 

// 	cin >> n >> k ; 

// 	for(int i = 0 ; i < n-1 ; i++){
// 		int a, b, c ; 
// 		cin >> a >> b >> c ; 
// 		grafo[a].push_back({b, c}), grafo[b].push_back({a, c}) ; 
// 	}

// 	for(int i = 1 ; i <= k ; i++) f[i] = inf ; 

//     make_graph(0, -1) ; 
  
//     cout << ans << "\n" ; 

// }

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