제출 #1123480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123480		pcc	경주 (Race) (IOI11_race)	C++17	100 / 100	528 ms	39680 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;
vector<pii> tree[mxn];
int dp[mxn*10];
int sz[mxn];
int dep[mxn];
int len[mxn];
bool del[mxn];
int K,N;
int ans = mxn*10;

void dfs1(int now,int par){
	sz[now] = 1;
	for(auto [nxt,w]:tree[now]){
		if(nxt == par||del[nxt])continue;
		dfs1(nxt,now);
		sz[now] += sz[nxt];
	}
	return;
}
int find_centroid(int now,int par,int tar){
	for(auto [nxt,w]:tree[now]){
		if(nxt == par||del[nxt])continue;
		if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
	}
	return now;
}
void dfs2(int now,int par){
	if(K>=len[now])ans = min(ans,dep[now]+dp[K-len[now]]+1);
	for(auto [nxt,w]:tree[now]){
		if(nxt == par||del[nxt])continue;
		dep[nxt] = dep[now]+1;
		len[nxt] = len[now]+w;
		dfs2(nxt,now);
	}
	return;
}
void dfs3(int now,int par){
	if(len[now]<mxn*10)dp[len[now]] = min(dp[len[now]],dep[now]);
	for(auto [nxt,w]:tree[now]){
		if(nxt == par||del[nxt])continue;
		dfs3(nxt,now);
	}
	return;
}
void dfs4(int now,int par){
	if(len[now]<mxn*10)dp[len[now]] = mxn*10;
	for(auto [nxt,w]:tree[now]){
		if(nxt == par||del[nxt])continue;
		dfs4(nxt,now);
	}
	return;
}

void cd(int now){
	dfs1(now,now);
	now = find_centroid(now,now,(sz[now]-1)>>1);
	len[now] = 0;
	dp[0] = 0;
	for(auto [nxt,w]:tree[now]){
		if(del[nxt])continue;
		dep[nxt] = 1;
		len[nxt] = w;
		dfs2(nxt,now);
		dfs3(nxt,now);
	}
	dfs4(now,now);
	del[now] = 1;
	for(auto [nxt,w]:tree[now]){
		if(!del[nxt])cd(nxt);
	}
	return;
}

int best_path(int n, int k, int H[][2], int L[]){
	N = n,K = k;
	fill(dp,dp+mxn*10,mxn*10);
	for(int i = 0;i+1<N;i++){
		int a = H[i][0],b = H[i][1],c = L[i];
		tree[a].push_back(pii(b,c));
		tree[b].push_back(pii(a,c));
	}
	cd(0);
	return (ans>N?-1:ans-1);
}

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