제출 #94653

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

race

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
#define INF 1e9
using namespace std;

int n,k;
vector<pii> edge[222222];
int siz[222222];

set<int> st;
vector<pii> vc;
int cnt[1111111];
bool is_cent[222222];

int ans=INF;

int dfs_siz(int v,int p){
	siz[v]=1;
	for(pii u:edge[v]){
		if(u.ff==p || is_cent[u.ff]) continue;
		siz[v]+=dfs_siz(u.ff,v);
	}
	return siz[v];
}

int cent(int rt){
	int v=rt,p=rt;
	
	while(1){
		int mx=-1,mxi;
		for(pii u:edge[v]){
			if(u.ff==p || is_cent[u.ff]) continue;
			if(mx<siz[u.ff]){
				mx=siz[u.ff];
				mxi=u.ff;
			}
		}
		if(mx==-1 || mx<=siz[rt]/2) break;
		p=v; v=mxi;
	}
	return v;
}

void dfs_dist(int v,int p,int dist1,int dist2){
	vc.push_back({dist1,dist2});

	for(pii u:edge[v]){
		if(u.ff==p || is_cent[u.ff]) continue;
		if(dist1+u.ss<=k) dfs_dist(u.ff,v,dist1+u.ss,dist2+1);
	}
}

void cent_dnc(int v){
	dfs_siz(v,v);
	v=cent(v); is_cent[v]=1;

	//printf("%d\n",v);

	st.clear();
	st.insert(0); cnt[0]=0;
	for(pii u:edge[v]){
		if(is_cent[u.ff] || u.ss>k) continue;

		vc.clear();
		dfs_dist(u.ff,v,u.ss,1);

		//for(pii dist:vc) printf("%d %d\n",dist.ff,dist.ss);

		for(pii dist:vc){
			if(st.find(k-dist.ff)!=st.end()) ans=min(ans,cnt[k-dist.ff]+dist.ss);
		}

		for(pii dist:vc){
			if(st.find(dist.ff)==st.end()){
				st.insert(dist.ff);
				cnt[dist.ff]=dist.ss;
			}
			else cnt[dist.ff]=min(cnt[dist.ff],dist.ss);
		}

		//printf("%d\n\n",ans);
	}

	for(pii u:edge[v]){
		if(is_cent[u.ff]) continue;
		cent_dnc(u.ff);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N; k=K;

	for(int i=0;i<n-1;i++){
		edge[H[i][0]].push_back({H[i][1],L[i]});
		edge[H[i][1]].push_back({H[i][0],L[i]});
	}

	cent_dnc(0);

	if(ans==INF) return -1;
	return ans;
}

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