Submission #871618

#	Time	Username	Problem	Language	Result	Execution time	Memory
871618		dsyz	Race (IOI11_race)	C++17	100 / 100	395 ms	111396 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define MAXN (200005)
ll n,k;
ll ans = 1e18;
vector<pair<ll,ll> > v[MAXN];
map<ll,ll> m[MAXN];
pair<ll,ll> offset[MAXN];
void dfs(ll x,ll p){
	m[x][0] = 0;
	for(auto u : v[x]){
		if(u.first != p){
			dfs(u.first,x);
			offset[u.first].first += u.second;
			offset[u.first].second++;
			if(m[u.first].size() > m[x].size()){
				swap(m[u.first],m[x]);
				swap(offset[u.first],offset[x]);
			}
			for(auto a : m[u.first]){
				ll t = k - a.first - offset[x].first - offset[u.first].first;
				if(m[x].count(t)) ans = min(ans,m[x][t] + offset[x].second + a.second + offset[u.first].second);
			}
			for(auto a : m[u.first]){
				ll t = a.first + offset[u.first].first - offset[x].first;
				if(m[x].count(t)) m[x][t] = min(m[x][t],a.second + offset[u.first].second - offset[x].second);
				else m[x][t] = a.second + offset[u.first].second - offset[x].second;
			}
		}
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(ll i = 0;i < N - 1;i++){
		ll a = H[i][0];
		ll b = H[i][1];
		ll c = L[i];
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	dfs(0,-1);
	if(ans == 1e18) return -1;
	else return ans;
}

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