Submission #1274549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274549		almaz	Race (IOI11_race)	C++20	0 / 100	11 ms	2824 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ar array

const int MOD = 1e9 + 7,INF = 1e9, N = 2e5 + 5;
int n , k, ans = INF;	
vector <vector<pair<int,int>>> g;
vector <int> del, sub_sz;
vector <int> mp(10000, INF);
vector <pair<int,int>> sum;

void dfs(int v,int p){
	sub_sz[v] = 1;
	for(auto [i , c] : g[v]){
		if(i == p || del[i]) continue;
		
		dfs(i , v);
		sub_sz[v] += sub_sz[i];
	}
}

int cent(int v, int p, int m){
	// cout<<"HERE "<<v<<endl;
	for(auto [i , c] : g[v]){
		if(sub_sz[i] * 2 > m && !del[i] && i != p){
			return cent(i, v, m);
		}
	}
	return v;
}

void bfs(int x, int p){
	// cout<<x<<' ' << p<<endl;
	for(auto [i , c] : g[x]){
		if(i == p || del[i]) continue;
		
		sum[i].ff = sum[x].ff + c;
		sum[i].ss = sum[x].ss + 1;
		int h = k - sum[i].ff;
		if(h >= 0){
			ans = min(ans , mp[h] + sum[i].ss);
		}
		bfs(i, x);
	}
}

void add(int x , int p){
	for(auto [i , c] : g[x]){
		if(i == p || del[i]) continue;
		mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
		add(i , x);
	}
}

void dec(int v , int m){
	// cout<<v<<endl;
	dfs(v , v);
	// for(int i = 0;i < n;i++){
		// cout<<sub_sz[i]<<' ';
	// }
	// cout<<endl;
	int cen = cent(v, v , m);
	// cout<<cen<<endl;
	mp[0] = 0;
	
	
	del[cen] = 1;
	for(auto [i , c] : g[cen]){
		if(del[i]) continue;
		sum[i].ff = c;
		sum[i].ss = 1;
		bfs(i , i);
		mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
		int h = k - sum[i].ff;
		if(h >= 0){
			ans = min(ans , mp[h] + sum[i].ss);
		}
		add(i, i);
		// cout<<endl;
	}
	mp.clear();
	mp.resize(10000, INF);
	sum.clear();
	sum.resize(N + 1);
	sub_sz.clear();
	sub_sz.resize(N + 1, 0);
	for(auto [i , c] : g[cen]){
		if(del[i]) continue;
		dec(i, sub_sz[i]);
	}
}

int best_path(int N1, int K, int H[][2], int L[]){
	n = N1;
	k = K;
	// if(n == 100){
		// while(true);
	// }
	g.resize(n + 1);
	del.resize(n + 1);
	sub_sz.resize(n + 1);
	sum.resize(n + 1);
	
	for(int i = 0;i < n - 1;i++){
		int a = H[i][0], b = H[i][1] , c = L[i];
		
		g[a].pb({b , c});
		g[b].pb({a , c});
	}
	
	dec(1, n);
	if(ans == INF){
		return -1;
	}
	return ans;
}

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