Submission #922238

#	Time	Username	Problem	Language	Result	Execution time	Memory
922238		Nurislam	Race (IOI11_race)	C++17	43 / 100	3102 ms	39364 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 k;
unordered_map<int,int> mp;
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, bool ok){
	if(sum > k)return;
    if (!ok){
        if ( sum == k ) ans = min(ans, dep);
        else ans = min(ans, !mp.count(k-sum) ? inf : mp[k-sum]+dep);
    }else{
        if ( !mp.count(sum) ) mp[sum] = dep;
        else mp[sum] = min(mp[sum], dep);
    }
    for(auto [to, w]:g[v]){
        if (us[to] || to == pr)continue;
        dfs(to, v, dep+1, sum+w, ok);
    }
}
void fun(int v){
	m = dfs_sz(v, -1);
	m = dfs_ctr(v, -1);
	us[ctr] = 1;
	mp.clear();
	for(auto [to, cst]:g[ctr]){
		if(us[to])continue;
		dfs(to, ctr, 1, cst, 0);
		dfs(to, ctr, 1, cst, 1);
	}
	for(auto [to, cst]:g[ctr]){
		if(us[to])continue;
		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]});
	}
	k = K;
	fun(0);
	return (ans == inf?-1:ans);
}

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