Submission #319860

#	Time	Username	Problem	Language	Result	Execution time	Memory
319860		nandonathaniel	Race (IOI11_race)	C++14	100 / 100	577 ms	100452 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
const int MAXN=200005;
typedef pair<int,int> pii;
long long pref[MAXN];
vector<pii> adj[MAXN];
int depth[MAXN],KK,ans=1e9;
map<long long,int> subtree[MAXN];

void merge(int now,int nxt){
	for(map<long long,int>::iterator it=subtree[nxt].begin();it!=subtree[nxt].end();++it){
		if(subtree[now].count(it->first))subtree[now][it->first]=min(subtree[now][it->first],it->second);
		else subtree[now][it->first]=it->second;
	}
}

void dfs(int now,int par){
	subtree[now][pref[now]]=depth[now];
	//hitung semua pasangan node yang LCAnya now
	for(auto nxt : adj[now]){
		if(nxt.fi==par)continue;
		depth[nxt.fi]=depth[now]+1;
		pref[nxt.fi]=pref[now]+nxt.se;
		dfs(nxt.fi,now);
		if(subtree[now].size()<subtree[nxt.fi].size())subtree[now].swap(subtree[nxt.fi]);
	}
	for(auto nxt : adj[now]){
		if(nxt.fi==par)continue;
		for(map<long long,int>::iterator it=subtree[nxt.fi].begin();it!=subtree[nxt.fi].end();++it){
			int sisa=KK+2*pref[now]-it->first;
			if(subtree[now].count(sisa)){
				ans=min(ans,it->second+subtree[now][sisa]-2*depth[now]);
			}
		}
		merge(now,nxt.fi);
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	KK=K;
	for(int i=0;i<N-1;i++){
		adj[H[i][0]].push_back({H[i][1],L[i]});
		adj[H[i][1]].push_back({H[i][0],L[i]});
	}
	dfs(0,-1);
	if(ans==1e9)ans=-1;
	return ans;
}

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