Submission #47056

#	Time	Username	Problem	Language	Result	Execution time	Memory
47056		wzy	Race (IOI11_race)	C++11	100 / 100	869 ms	96700 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int n ,k ;
vector<pii> adj[200005];
long long ans = (long long) 1e18;
int sz[200005];
int dp[200005];
map<long long, int> tree[200005];
void pre_dfs(int x , int y){
	sz[x] = 1;
	dp[x] = dp[y]  + 1;
	for(int i = 0 ; i < adj[x].size() ; i++){
		pii v = adj[x][i];
		if(v.F == y) continue;
		pre_dfs(v.F, x);
		sz[x] += sz[v.F];
	}
	int maxxi = -1 , optmaxi = 0;
	for(int i = 0 ; i < adj[x].size() ; i++){
		pii v = adj[x][i];
		if(v.F == y){
			continue;
		}
		if(sz[v.F] >= maxxi){
			optmaxi = i;
			maxxi = sz[v.F];
		}
	}
	if(x == y || adj[x].size() > 1)
	swap(adj[x][0] , adj[x][optmaxi]);
}

void solve(int x , int y , long long d){
	if(adj[x].size() == 1 && adj[x][0].F == y){
		tree[x][d] = dp[x];
		if(d == k) ans = min(ans , (long long) dp[x]);
	}
	else{
		solve(adj[x][0].F , x , d + adj[x][0].S);
		swap(tree[x] , tree[adj[x][0].F]);
		for(int j = 1 ; j < adj[x].size() ; j++){
			pii v = adj[x][j];
			if(v.F == y) continue;
			solve(v.F , x , v.S + d);
			long long opt = k + 2*d;
			queue<pii> q;
			for(auto p : tree[v.F]){
				if(tree[x].count(opt - p.F)){
					ans = min(ans , (long long) p.S + tree[x][opt-p.F]- 2*dp[x]);
				}
				q.push(p);
			}
			while(!q.empty()){
				pii p = q.front();
				q.pop();
				if(tree[x].count(p.F)) tree[x][p.F] = min(tree[x][p.F] , p.S);
				else
				tree[x][p.F] = p.S;
			}
			tree[v.F].clear();
		}
		if(tree[x].count(d)) tree[x][d] = min(tree[x][d] , dp[x]);
		else tree[x][d] = dp[x];
		if(tree[x].count(d + k)){ ans = min(ans , (long long) tree[x][d+k] - dp[x]);}
	}
}


int best_path(int N, int K, int H[][2], int L[]){
	n = N , k = K;
	for(int i = 0 ; i < n -1 ; i ++){
		int x , y , z;
		scanf("%d%d%d" , &x , &y , &z);
		adj[H[i][0]].pb(pii(H[i][1],L[i]));
		adj[H[i][1]].pb(pii(H[i][0],L[i]));
	}
	dp[0] = -1;
	pre_dfs(0 , 0);
	solve(0 , 0 , 0);
	if(ans == (long long) 1e18) return -1;
	else return ans;

}

Compilation message (stderr)

race.cpp: In function 'void pre_dfs(int, int)':
race.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[x].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[x].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int, int, long long int)':
race.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1 ; j < adj[x].size() ; j++){
                   ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &x , &y , &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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