Submission #361358

#	Time	Username	Problem	Language	Result	Execution time	Memory
361358		ronnith	Race (IOI11_race)	C++14	0 / 100	6 ms	9728 KiB

race

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

using namespace std;
using ll = long long;

#define f first
#define s second

const int NN = 200000;
const int MX = 1000000;

int n, k, sz[NN];

ll level[NN], ANS = INT_MAX, dist[NN];

map<ll, ll> min_edges;

vector<int> nodes[NN];

vector<pair<int, int>> adj[NN];



void dfs_pre(int x, int pr, int lvl, ll sm) {
	sz[x] = 1, level[x] = lvl, dist[x] = sm;
	for(auto e : adj[x]) if(e.f != pr) {
		dfs_pre(e.f, x, lvl + 1, sm + e.s);
		sz[x] += sz[e.f];
	}
}



void dfs(int x, int pr, bool keep) {
	int mx = 0, big_child = -1;
	
	for(auto e : adj[x])
		if(e.f != pr)
			if(sz[e.f] > mx) {
				mx = sz[e.f];
				big_child = e.f;
			}

	if(big_child == -1) {
		nodes[x].push_back(x);
		if(keep)
			min_edges[dist[x]] = level[x];
		return;
	}
	
	for(auto e : adj[x])
		if(e.f != pr && e.f != big_child)
			dfs(e.f, x, false);
	
	dfs(big_child, x, true);
	swap(nodes[x], nodes[big_child]);
	nodes[x].push_back(x);

	if(min_edges.find(dist[x]) == min_edges.end()) min_edges[dist[x]] = level[x];
	else  min_edges[dist[x]] = min(min_edges[dist[x]], level[x]);
	
	if(min_edges.find(dist[x] + k) != min_edges.end())
		ANS = min(ANS, min_edges[dist[x] + k]);

	for(auto e : adj[x])
		if(e.f != pr && e.f != big_child)
			for(auto nd : nodes[e.f]) {
				ll d = dist[nd] - dist[x];
				int lvl = level[nd] - level[x];
			
				if(d == k) ANS = min(ANS, ll(lvl));
				else if(d < k && min_edges.find(k - d + dist[x]) != min_edges.end())
					ANS = min(ANS, min_edges[k - d + dist[x]] - level[x] + lvl);
			
				if(min_edges.find(dist[nd]) == min_edges.end()) min_edges[dist[nd]] = level[nd];
				else min_edges[dist[nd]] = min(min_edges[dist[x]], level[nd]);
				
				nodes[x].push_back(nd);
			}

	if(!keep) 
		for(auto& e : min_edges)
			e.s = INT_MAX;
}



int best_path(int _N, int K, int H[][2], int L[]) {
	n = _N, k = K;
	for(int i = 0;i < n - 1;i ++) {
		adj[H[i][0]].emplace_back(H[i][1], L[i]);
		adj[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	dfs_pre(0, -1, 0, 0);
	dfs(0, -1, true);
	return (ANS == INT_MAX ? -1 : ANS);
}

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