Submission #1144551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144551		zhasyn	Race (IOI11_race)	C++20	0 / 100	3 ms	5184 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pll pair <ll, ll>
const ll N = 2 * 1e5 + 100, M = 1e6 + 100;
vector <pll> q[N];
int k, ans = INT_MAX;
bool was[N];
int need[N], cnt[N];
void dfs(int v, int pred){
	cnt[v] = 1;
	for(auto u : q[v]){
		if(u.F == pred) continue;
		dfs(u.F, v);
		cnt[v] += cnt[u.F];
	}
}
int get(int v, int p){
	for(auto u : q[v]){
		if(u.F == p || was[u.F]) continue;
		if(cnt[u.F] * 2 >= cnt[v]) return get(u.F, v);
	}
	return v;
}
vector <int >vec;
void obs(int v, int pred, int sum, int ct, int code){
	if(sum == k) ans = min(ans, ct);
	if(sum < k){
		if(code == 0){
			if(need[k - sum] != 0) ans = min(ans, ct + need[k - sum]);
		} else{
			if(need[sum] == 0) need[sum] = ct;
			else need[sum] = min(need[sum], ct);
			vec.pb(sum);
		}
	}
	
	for(auto u : q[v]){
		if(was[u.F] || pred == u.F) continue;
		obs(u.F, v, sum + u.S, ct + 1, code);
	}
}
void centroid(int v){
	v = get(v, -1);
	was[v] = true;
	for(auto u : q[v]){
		obs(u.F, u.S, 0, 1, 0);
		obs(u.F, u.S, 0, 1, 1);
	}
	for(auto u : vec){
		need[u] = 0;
	}
	for(auto u : q[v]){
		if(was[u.F]) continue;
		centroid(u.F);
	}
}
int best_path(int n, int gk, int h[][2], int l[]){
	k = gk;
  for(int i = 0; i < n - 1; i++){
	q[h[i][0]].pb({h[i][1], l[i]});
	q[h[i][1]].pb({h[i][0], l[i]});
  }
  dfs(1, -1);
  centroid(1);
  if(ans == INT_MAX) return -1;
  return ans;
}


// int main(){
// 	
	// return 0;
// }

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