Submission #319961

#	Time	Username	Problem	Language	Result	Execution time	Memory
319961		sofapuden	Race (IOI11_race)	C++14	9 / 100	245 ms	47076 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

typedef long long ll;

const int maxn = 2e5+5;

map<ll,int> se[maxn];
int dep[maxn];
int val[maxn];
vector<vector<pair<int,int>>> adj;

int ans = 1<<30, gK;

void dfs(int nod, int par){
	se[nod][val[nod]] = dep[nod];
	for(auto nxt : adj[nod]){
		if(nxt.first == par)continue;
		dep[nxt.first] = dep[nod]+1;
		val[nxt.first] = val[nod]+nxt.second;
		dfs(nxt.first,nod);
		if(se[nod].size() < se[nxt.first].size())swap(se[nod], se[nxt.first]);
	}
	for(auto nxt : adj[nod]){
		if(nxt.first == par)continue;
		for(auto it : se[nxt.first]){
			int missing = gK + 2*val[nod] - it.first;
			if(se[nod][missing]){
				ans = min(ans, it.second + se[nod][missing] - 2*dep[nod]);
			}
		}
		for(auto it : se[nxt.first]){
			if(se[nod][it.first])se[nod][it.first] = min(se[nod][it.first], it.second);
			else se[nod][it.first] = it.second;
		}
	}
	
}

int best_path(int N, int K, int H[][2], int L[]){
	memset(dep,1,sizeof dep);
	gK = K;
	adj.resize(N);
	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,0);
	if(ans == (1<<30))return -1;
	return ans;	
}
	

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