Submission #483982

#	Time	Username	Problem	Language	Result	Execution time	Memory
483982		PoPularPlusPlus	Race (IOI11_race)	C++17	100 / 100	409 ms	34420 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
 
const int N = 200002;
vector<pair<int,int>> adj[N];
int k;
int siz[N];
bool vis[N];
int cnt[1000003];
int ans;
vector<int> v;
 
void subtree(int node , int par = -1){
	siz[node] = 1;
	for(auto i : adj[node]){
		if(!vis[i.vf] && i.vf != par){
			subtree(i.vf , node);
			siz[node] += siz[i.vf];
		}
	}
}
 
int get(int node , int par , int need){
	for(auto i : adj[node]){
		if(!vis[i.vf] && i.vf != par && siz[i.vf] > need){
			return get(i.vf , node , need);
		}
	}
	return node;
}
 
void cal(int node , int par , int depth , int cur , int fill){
	if(cur > k)return;
	if(fill){
		ans = min(ans , depth + cnt[k - cur]);
	}
	else {
		cnt[cur] = min(cnt[cur] , depth);
		v.pb(cur);
	}
	for(auto i : adj[node]){
		if(!vis[i.vf] && i.vf != par){
			cal(i.vf , node , depth + 1 , i.vs + cur , fill);
		}
	}
}
 
void centriod(int node){
	subtree(node);
	int cen = get(node , -1 , siz[node]/2);
	cnt[0] = 0;
	v.clear();
	for(auto i : adj[cen]){
      	if(!vis[i.vf]){
		cal(i.vf , cen , 1 , i.vs , 1);
		cal(i.vf , cen , 1 , i.vs , 0);
        }
	}
	//cout << cen << ' ' << ans << '\n';
	for(int i : v)cnt[i] = 1e9;
	vis[cen] = 1;
	for(auto i : adj[cen]){
		if(!vis[i.vf]){
			centriod(i.vf);
		}
	}
}
 
int best_path(int n , int k1 , int h[][2], int l[]){
	for(int i = 0; i < n-1; i++){
		adj[h[i][0]].pb(mp(h[i][1] , l[i]));
		adj[h[i][1]].pb(mp(h[i][0] , l[i]));
	}
	k = k1;
	memset(vis,0,sizeof vis);
	for(int i = 0; i <= k; i++){
		cnt[i] = 1e9;
	}
	ans = 1e9;
	centriod(0);
	return(ans == 1e9 ? -1 : ans);
}

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