Submission #135783

#	Time	Username	Problem	Language	Result	Execution time	Memory
135783		Sorting	Race (IOI11_race)	C++14	100 / 100	761 ms	49768 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;
}
 
/*int _h[N][2], _l[N];
 
int main(){
	int _n, _k;
 
	cin >> _n >> _k;
 
	for(int i = 0; i < _n - 1; i++){
		cin >> _h[i][0] >> _h[i][1] >> _l[i];
 	}
 
 	cout << best_path(_n, _k, _h, _l) << "\n";
 
 	return 0;
}*/
/*
10 5
0 1 2
1 2 1
2 3 2 
3 4 3
4 5 1
5 6 5
6 7 1 
7 8 2
8 9 3
*/
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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