Submission #820166

#	Time	Username	Problem	Language	Result	Execution time	Memory
820166		PenguinsAreCute	Race (IOI11_race)	C++17	100 / 100	393 ms	106956 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re first
#define im second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define MAXN 200069
#define INF 314159265358979323
int ans=INF,k;
vii adj[MAXN];
int lazy_dist[MAXN], lazy_highways[MAXN];
map<int,int> min_dist[MAXN];
void dfs(int x, int p) {
	min_dist[x][0]=0;
	for(auto i: adj[x]) if(i.re!=p) {
		dfs(i.re, x);
		lazy_dist[i.re]+=i.im;
		lazy_highways[i.re]++;
		if(min_dist[i.re].size()>min_dist[x].size()) {
			swap(min_dist[i.re], min_dist[x]);
			swap(lazy_dist[i.re], lazy_dist[x]);
			swap(lazy_highways[i.re], lazy_highways[x]);
		}
		for(auto it: min_dist[i.re]) {
			int rem=k-it.re-lazy_dist[i.re]-lazy_dist[x];
			if(min_dist[x].count(rem)) ans=min(ans, it.im+min_dist[x][rem]+lazy_highways[i.re]+lazy_highways[x]);
		}
		for(auto it: min_dist[i.re]) {
			int insPt=it.re+lazy_dist[i.re]-lazy_dist[x], insV=it.im+lazy_highways[i.re]-lazy_highways[x];
			if(min_dist[x].count(insPt)) min_dist[x][insPt]=min(min_dist[x][insPt],insV);
			else min_dist[x][insPt]=insV;
		}
	}
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
	REP(i,0,N-1) {
		adj[H[i][0]].pb(ii(H[i][1],L[i]));
		adj[H[i][1]].pb(ii(H[i][0],L[i]));
	}
	k=K;
	dfs(0,-1);
	return ((ans==INF)?-1:ans);
}

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