Submission #922221

#	Time	Username	Problem	Language	Result	Execution time	Memory
922221		Nurislam	Race (IOI11_race)	C++17	0 / 100	2 ms	9560 KiB

race

#include "race.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;
const int inf = 1e9, mxN = 2e5+2;

vii g[mxN];
int us[mxN];
int m, ctr, ans = inf;
int n, k, k2;
int dfs_sz(int v, int pr){
	if(us[v])return 0;
	int s = 1;
	for(auto [to, cst]:g[v]){
		if(to == pr)continue;
		s += dfs_sz(to, v);
	}
	return s;
}
int dfs_ctr(int v, int pr){
	if(us[v])return 0;
	int s = 1;
	bool ok = 1;
	for(auto [to, cst]:g[v]){
		if(to == pr)continue;
		int sto = dfs_ctr(to, v);
		if(sto > m/2)ok = 0;
		s += sto;
	}
	if(s < m/2)ok = 0;
	if(ok)ctr = v;
	return s;
}
void dfs(int v, int pr, int dep, int sum, vector<pair<int,int>> &ds){
	if(us[v] || sum > k)return;
	ds.pb({sum, dep});
	for(auto [to, cst]:g[v]){
		if(to == pr)continue;
		dfs(to, v, dep+1, sum + cst, ds);
	}
}
void calc(int &v){
	unordered_map<int,int> mp;
	for(auto [to, cst]:g[v]){
		if(us[to])continue;
		vector<pair<int,int> > ds;
		dfs(to, v, 1, 0, ds);
		for(auto j:ds)ans = min(ans, (mp[k-j.ff] == 0 ? inf : mp[k-j.ff])  +  j.ss);
		for(auto j:ds){
			if(mp[j.ff] == 0)mp[j.ff] = j.ss;
			else mp[j.ff] = min(mp[j.ff], j.ss);
		}
	}
}
void fun(int v){
	m = dfs_sz(v, -1);
	m = dfs_ctr(v, -1);
	us[ctr] = 1;
	calc(ctr);
	for(auto [to, cst]:g[ctr]){
		if(!us[to])fun(to);
	}
}
int best_path(int n, int k, int h[][2], int l[])
{
	for(int i = 0; i < n-1; i++){
		g[h[i][0]].pb({h[i][1], l[i]});
		g[h[i][1]].pb({h[i][0], l[i]});
	}
	fun(0);
	return ans;
}

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