Submission #136595

#	Time	Username	Problem	Language	Result	Execution time	Memory
136595		dolphingarlic	경주 (Race) (IOI11_race)	C++14	100 / 100	1031 ms	52748 KiB

race

#include <bits/stdc++.h>
//#include "race.h"
 
using namespace std;
 
const int N = 2e5 + 7;
const int inf = 1e9;
const int K = 1e6 + 7;
const int T = 1e8;
 
int n, k;
vector <int> adj[N], len[N], adj_c[N], rv;
int sz[N];
 
bool used[N];
 
int find_cnt(int u, int p = -1){
	sz[u] = 1;
 
	for(int to: adj[u]){
		if(p == to || used[to]){
			continue;
		}
 
		sz[u] += find_cnt(to, u);
	}
 
	return sz[u];
}
 
int find_centroid(int u, int cnt, int p = -1){
	for(int to: adj[u]){
		if(to == p || used[to]){
			continue;
		}
 
		if(sz[to] > (cnt / 2)){
			return find_centroid(to, cnt, u);
		}
	}
 
	return u;
}	
 
int root;
 
void decompose(int u, int p = -1){
	int cnt = find_cnt(u);
	int cen = find_centroid(u, cnt);
 
	//cout << p << " -> " << cen << endl;
 
	if(p != -1){
		adj_c[p].push_back(cen);
	}
	else{
		root = cen;
	}
 
	used[cen] = true;
	for(int to: adj[cen]){
		if(!used[to]){
			decompose(to, cen);
		}
	}
	used[cen] = false;
}
 
int arr[K];
vector<pair<int, int> > vec;
 
int ans = inf;
 
void solve_k(int u, int pr, int sum, int d){
	if(sum > k || used[u]){
		return;
	}
 
	vec.push_back({sum, d});
	if(arr[k - sum] != inf){
		ans = min(ans, d + arr[k - sum]);
	}
 
	for(int i = 0; i < adj[u].size(); i++){
		int to = adj[u][i];
		int l = len[u][i];
 
		if(used[to] || to == pr){
			continue;
		}
 
		solve_k(to, u, sum + l, d + 1);
	}
}
 
int sum_vec = 0;
 
clock_t t;
 
inline float time_passed(){
	return (float)(clock() - t) / (float)CLOCKS_PER_SEC;
}
 
void solve(int u){
	used[u] = true;
	for(int to: adj_c[u]){
		solve(to);
	}
	rv.clear();
 
	/*if(time_passed() > (float)2.7){
		return;
	}*/
	
	for(int i = 0; i < adj[u].size(); i++){
		vec.clear();
		solve_k(adj[u][i], u, len[u][i], 1);
 
		sum_vec += vec.size();
 
		for(pair<int, int> p: vec){
			if(arr[p.first] == inf){
				rv.push_back(p.first);
			}
			arr[p.first] = min(arr[p.first], p.second);
		}
	}
 
	for(int i: rv){
		arr[i] = inf;
	}
	
	used[u] = false;
}
 
 
 
int best_path(int _n, int _k, int _h[][2], int _l[]){
 	t = clock();
 
	n = _n;
	k = _k;
 
	for(int i = 0; i < n - 1; i++){
		adj[_h[i][0]].push_back(_h[i][1]);
		adj[_h[i][1]].push_back(_h[i][0]);
 
		len[_h[i][0]].push_back(_l[i]);
		len[_h[i][1]].push_back(_l[i]);
	}
 
	decompose(0);
 
	for(int i = 1; i < K; i++){
		arr[i] = inf;
	}
 
	solve(root);
 
	/*if(sum_vec > T){
		return -21;
	}*/
 
	if(ans == inf){
		return -1;
	}
 
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void solve_k(int, int, int, int)':
race.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++){
                 ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++){
                 ~~^~~~~~~~~~~~~~~

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