제출 #233977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233977		amiratou	경주 (Race) (IOI11_race)	C++14	100 / 100	1867 ms	83400 KiB

race

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fi first
#define se second
#define ll long long

bool dead[200005];
int s[200005],n,k;
ll ans=LLONG_MAX;
vector<vector<pair<int,int> > > vec;
map<ll,multiset<int> > mymap;
vector<map<ll,int> > best;
int dfs(int node,int p,int s_p,bool flag=0,int d=0,ll h=0){
	if(flag&&(s_p!=-1)){
		if(best[s_p].count(h))best[s_p][h]=min(best[s_p][h],d);
		else best[s_p][h]=d;
	}
	s[node]=1;
	for(auto it:vec[node])
		if(it.fi!=p&&!dead[it.fi])
			s[node]+=dfs(it.fi,node,((!d)?it.fi:s_p),flag,d+1,h+it.se);
	return s[node];
}
int find_cetroid(int node,int p){
	for(auto it:vec[node])
		if(it.fi!=p&&!dead[it.fi]&&s[it.fi]>(n/2))
			return find_cetroid(it.fi,node);
	return node;
}
void solve(int node){
	n=dfs(node,node,-1);
	int r=find_cetroid(node,node);
	mymap.clear();
	dfs(r,r,-1,1);
	for(auto it:vec[r]){
		if(dead[it.fi])continue;
		for(auto it2:best[it.fi])
			mymap[it2.fi].insert(it2.se);
	}
	for(auto it:vec[r]){
		if(dead[it.fi])continue;
		for(auto it3:best[it.fi]){
			if(it3.fi>k)break;
			if(!mymap.count(k-it3.fi))continue;
			auto hk=mymap[k-it3.fi].begin();
			if((best[it.fi].count(k-it3.fi))&&((*hk)==best[it.fi][k-it3.fi]))hk++;
			if(hk!=mymap[k-it3.fi].end())ans=min(ans,(ll)(*hk)+it3.se);
		}
		if(best[it.fi].count(k))ans=min(ans,(ll)best[it.fi][k]);
		best[it.fi].clear();
	}
	dead[r]=1;
	for(auto it:vec[r])
		if(!dead[it.fi])
			solve(it.fi);
}

int best_path(int N, int K, int H[][2], int L[])
{
	best.resize(N);
	k=K;
	vec.resize(N);
	for (int i = 0; i < N-1; ++i)
	{
		vec[H[i][0]].push_back({H[i][1],L[i]});
		vec[H[i][1]].push_back({H[i][0],L[i]});
	}
	solve(0);
	return ((ans==LLONG_MAX)?(-1):ans);
}

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