oj.uz

Submission #135155

# Submission time Handle Problem Language Result Execution time Memory
135155 2019-07-23T17:19:01 Z Sorting Race (IOI11_race) C++14
0 / 100
 18 ms 18424 KB 
#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int N = 2e5 + 7;
const int inf = 1e9;
const int K = 1e6 + 7;

int n, k;
vector <int> adj[N], len[N], adj_c[N];
int sz[N];

bool used[N];
int link[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 << " cnt - " << cnt << endl;  

	if(p != -1){
		adj_c[p].push_back(cen);
	}
	if(u == 0){
		root = cen;
	}

	used[cen] = true;
	for(int to: adj[cen]){
		if(!used[to]){
			decompose(to, cen);
		}
	}
	used[cen] = false;
}

int arr[K];
vector<vector<pair<int, int> > > vec;

void solve_k(int u, int pr, int sum, int d){
	if(sum == k){
		return;
	}

	vec.back().push_back({sum, d});

	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 solve(int u){
	int ans = inf;

	used[u] = true;
	for(int to: adj_c[u]){
		ans = min(ans, solve(to));
	}

	vec.clear();
	for(int i = 0; i < adj[u].size(); i++){
		vec.push_back(vector<pair<int, int> >());

		solve_k(adj[u][i], u, len[u][i], 1);

		for(pair<int, int> p: vec.back()){
			if(arr[k - p.first] != inf){
				ans = min(ans, p.second + arr[k - p.first]);
			}
		}

		for(pair<int, int> p: vec.back()){
			arr[p.first] = min(arr[p.first], p.second);
		}
	}
	for(vector<pair<int, int> > vec2: vec){
		for(pair<int, int> p: vec2){
			if(p.first){
				arr[p.first] = inf;
			}
		}
	}
	vec.clear();

	return ans;
}

int best_path(int _n, int _k, int _h[][2], int _l[]){
	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;
	}

	int ans = solve(root);

	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;
}*/
/*
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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 18424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 18424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 18424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 18424 KB Output isn't correct
2 Halted 0 ms 0 KB -