Submission #753966

#	Time	Username	Problem	Language	Result	Execution time	Memory
753966		phoenix0423	Race (IOI11_race)	C++17	0 / 100	3 ms	4948 KiB

race

#include "race.h"

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 2e5 + 5;
ll n, k, ans = 1e9;
vector<pll> adj[maxn];
int w[maxn], vis[maxn], siz[maxn], h[maxn][2];
map<ll, ll> all, tmp;
// find centroid, calculate answer for centroid, remove the node and recurse for further centroids
void dfssz(int pos, int prev){
	siz[pos] = 1;
	for(auto [x, idx] : adj[pos]){
		if(x == prev || vis[x]) continue;
		dfssz(x, pos);
		siz[pos] += siz[x];
	}
}
void dfsans(int pos, int prev, ll dis, ll cnt){
	if(tmp.find(dis) != tmp.end()) tmp[dis] = min(tmp[dis], cnt);
	else tmp[dis] = cnt;
	for(auto [x, idx] : adj[pos]){
		if(x == prev || vis[x]) continue;
		dfsans(x, pos, dis + w[idx], cnt + 1);
	}
}
int get_centroid(int pos, int prev, int sz){
	for(auto [x, idx] : adj[pos]){
		if(x != prev && !vis[x] && siz[x] > sz / 2) return get_centroid(x, pos, sz);
	}
	return pos;
}
void centroid_decomposition(int pos){
	dfssz(pos, -1);
	int centroid = get_centroid(pos, -1, siz[pos]);
	vis[centroid] = 1;
	all.clear();
	all[0] = 0;
	for(auto [x, idx] : adj[centroid]){
		tmp.clear();
		if(vis[x]) continue;
		dfsans(x, -1, w[idx], 1);
		for(auto [dis, cnt] : tmp){
			if(all.find(k - dis) != all.end()) {
				ans = min(ans, cnt + all[k - dis]);
			}
		}
		for(auto [dis, cnt] : tmp){
			if(all.find(dis) != all.end()) all[dis] = min(all[dis], cnt);
			else all[dis] = cnt;
		}
	}
	for(auto [x, idx] : adj[centroid]){
		if(vis[x]) continue;
		centroid_decomposition(x);
	}
}
int best_path(int N, int K, int h[][2], int w[]){
	n = N, k = K;
	for(int i = 0; i < n - 1; i++){
		adj[h[i][0]].eb(h[i][1], i);
		adj[h[i][1]].eb(h[i][0], i);
	}
	centroid_decomposition(0);
	return (ans < 1e7 ? ans : -1);	
}/*
ll best_path(int n, int k, ll h[][2], ll w[]){
	for(int i = 0; i < n - 1; i++){
		adj[h[i][0]].eb(h[i][1], i);
		adj[h[i][1]].eb(h[i][0], i);
	}
	centroid_decomposition(0);
	return ans;
}
void read_input(){
	cin>>n>>k;
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin>>a>>b;
		adj[a].eb(b, i);
		adj[b].eb(a, i);
	}
	for(int i = 0; i < n - 1; i++) cin>>w[i];
}
int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);
	read_input();
	centroid_decomposition(0);
	ll ans = best_path(n, k, h, w);
	cout<<(ans > 1e7 ? -1 : ans)<<"\n";
}*/

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