Submission #1274594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274594		almaz	Race (IOI11_race)	C++20	0 / 100	3093 ms	4808 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(1000006, 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;
		if(sum[i].ff <= k) mp[sum[i].ff] = min(mp[sum[i].ff] , sum[i].ss);
		add(i , x);
	}
}

void dec(int v , int m){
	dfs(v , v);
	
	int cen = cent(v, v , m);
	
	mp.clear();
	mp.resize(1000006, INF);
	sum.clear();
	sum.resize(n);
	
	mp[0] = 0;
	
	for(auto [i , c] : g[cen]){
		if(del[i] && i != cen) continue;
		sum[i].ff = c;
		sum[i].ss = 1;
		bfs(i , cen);
		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, cen);
		// cout<<endl;
	}
	
	
	for(auto [i , c] : g[cen]){
		if(del[i]) continue;
		dfs(i , cen);
		dec(i, sub_sz[i]);
	}
}

int best_path(int N1, int K, int H[][2], int L[]){
	n = N1;
	k = K;
	ans = INF;
	g.clear();
	del.clear();
	sub_sz.clear();
	g.resize(n);
	del.resize(n);
	sub_sz.resize(n);
	
	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(0, n);
	
	if(ans == INF){
		return -1;
	}
	return ans;
}

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