Submission #361366

#	Time	Username	Problem	Language	Result	Execution time	Memory
361366		ronnith	Race (IOI11_race)	C++14	100 / 100	671 ms	68320 KiB

race

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

using namespace std;
using ll = long long;

#define f first
#define s second
#define nme(x) #x << " : " << x << ' '

const int NN = 200000;

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 && 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] - level[x]);
		// if(min_edges[dist[x] + k] - level[x] == 2) {
		// 	cerr << nme(x) << '\n';
		// }
	}

	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 && 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[k - d + dist[x]] - level[x] + lvl == 2) {
					// 	cerr << nme(x) << '\n';
					// 	if(x == 0) {
					// 		cerr << nme(d) << '\n';
					// 		cerr << min_edges[k - d + dist[x]] << '\n';
					// 		cerr << "yes";
					// 	}
					// }
				}
			}
			for(auto nd : nodes[e.f]) {
				if(min_edges.find(dist[nd]) == min_edges.end()) min_edges[dist[nd]] = level[nd];
				else min_edges[dist[nd]] = min(min_edges[dist[nd]], level[nd]);
				nodes[x].push_back(nd);
			}
		}

	// if(ANS == 2) {
	// 	cerr << nme(x) << '\n';
	// }

	// if(x == 6) {
	// 	cerr << nme(big_child) << '\n';
	// 	cerr << nme(ANS) << '\n';
	// }

	if(!keep) 
		min_edges.clear();
}



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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57