Submission #387873

#	Time	Username	Problem	Language	Result	Execution time	Memory
387873		pure_mem	Race (IOI11_race)	C++14	21 / 100	3071 ms	16288 KiB

race

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

#define X first
#define Y second
#define ll long long
#define MP make_pair

using namespace std;

const int MAXN = 2e5 + 12;

int answer, n, k, sz[MAXN];
vector< pair<int, int> > graph[MAXN];
set< pair<ll, int> > stAct, tmpAct;

void dfs_sz(int v, int pr){
	sz[v] = 1;
	for(pair<int, int> to: graph[v]){
		if(to.X != pr){
			dfs_sz(to.X, v);
			sz[v] += sz[to.X];
		}
	}	
}

void dfs_prep(int v, int pr, ll cost, int dist){
	if(cost > k)
		return;
	auto it = stAct.lower_bound(MP(k - cost, n + 1));
	if(prev(it)->X + cost == k){
		answer = min(answer, prev(it)->Y + dist);
	}
	for(pair<int, int> to: graph[v]){
		if(to.X == pr)
			continue;
		dfs_prep(to.X, v, cost + to.Y, dist + 1);
	}
}

void dfs_add(int v, int pr, ll cost, int dist){
	if(cost > k)
		return;
	auto it = stAct.lower_bound(MP(cost, 0));
	if(it != stAct.end() && it->X == cost && it->Y > dist)
		stAct.erase(it), stAct.insert(MP(cost, dist));		
	else if(it == stAct.end() || it->X != cost)
		stAct.insert(MP(cost, dist));
	for(pair<int, int> to: graph[v]){
		if(to.X == pr)
			continue;
		dfs_add(to.X, v, cost + to.Y, dist + 1);
	}
}

void dfs(int v, int pr, bool keep){
	int mx = 0, cost = 0;
	for(pair<int, int> to: graph[v]){
		if(to.X != pr && sz[mx] < sz[to.X])
			mx = to.X, cost = to.Y;
	}
	for(pair<int, int> to: graph[v]){
		if(to.X != pr && mx != to.X)
			dfs(to.X, v, 0);
	}
	if(mx){
		dfs(mx, v, 1);
		while(!stAct.empty()){
			auto cur = *stAct.begin();
			stAct.erase(stAct.begin());
			cur.X += cost, cur.Y += 1;
			if(cur.X > k)
				continue;
			else if(cur.X == k)
				answer = min(answer, cur.Y);
			else
				tmpAct.insert(cur);		
		} stAct.swap(tmpAct), tmpAct.clear();
	}
	stAct.insert(MP(0, 1));
	for(pair<int, int> to: graph[v]){
		if(to.X != pr && mx != to.X)
			dfs_prep(to.X, v, to.Y, 1), dfs_add(to.X, v, to.Y, 2);
	}
	if(!keep)
		stAct.clear();
}

int best_path(int N, int K, int H[][2], int L[]) {
	answer = N + 1, n = N, k = K;
	for(int i = 0;i < n;i++){
		graph[H[i][0] + 1].push_back(MP(H[i][1] + 1, L[i]));
		graph[H[i][1] + 1].push_back(MP(H[i][0] + 1, L[i]));
	}
	dfs_sz(1, 1);
	dfs(1, 1, 0);
	if(answer == N + 1)
		answer = -1;
	else
		answer -= 1;
	return answer;
}

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