Submission #384077

#	Time	Username	Problem	Language	Result	Execution time	Memory
384077		Drew_	Race (IOI11_race)	C++14	100 / 100	1506 ms	60504 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second

const int MAX = 2e5 + 7;
const int inf = 1e9 + 7;

int n, k;
int sz[MAX];
set<ii> adj[MAX];
static int ans;

int get_sz(int node, int par)
{
	sz[node] = 1;
	for (ii to : adj[node])
		if (to.f1 != par)
			sz[node] += get_sz(to.f1, node);
	return sz[node];
}

int centroid(int node, int par, int n)
{
	for (ii to : adj[node])
		if (to.f1 != par && sz[to.f1] > n/2)
			return centroid(to.f1, node, n);
	return node;
}

//{distance, length, id
vector<pair<int, ii>> vec;
void dfs(int node, int par, int id, int dist, int h, bool zero)
{
	if (dist > k)
		return;

	if (!zero) //prevent duplicate data
		vec.pb({dist, {h, id}});

	for (ii to : adj[node])
	{
		if (to.f1 != par)
			dfs(to.f1, node, id, dist + to.s2, h+1, to.s2 == 0);
	}
}

void rc(int node)
{
	int n = get_sz(node, -1);
	int c = centroid(node, -1, n);
	vector<ii> edge(adj[c].begin(), adj[c].end());

	vec.clear();
	vec.pb({0, {0, 0}});

	int id = 1;
	for (ii e : edge)
		dfs(e.f1, c, id++, e.s2, 1, false);

	sort(vec.begin(), vec.end());

	{
		vector<pair<int, ii>> nv;
		nv.pb(vec[0]);

		set<ii> inserted; //distance, id
		for (int i = 1; i < vec.size(); ++i)
		{
			if (!inserted.count({vec[i].f1, vec[i].s2.s2}))
			{
				inserted.insert({vec[i].f1, vec[i].s2.s2});
				nv.pb(vec[i]);
			}
		}
		vec = nv;
	}

	for (pair<int, ii> x : vec)
	{
		auto it = lower_bound(vec.begin(), vec.end(), mp(k - x.f1, mp(-1, -1)));
		if (it == vec.end())
			continue;

		if ((*it).s2.s2 == x.s2.s2)
			it = next(it);

		if (it == vec.end())
			continue;

		if ((*it).f1 != k - x.f1)
			continue;

		assert((*it).s2.s2 != x.s2.s2);
		ans = min(ans, (*it).s2.f1 + x.s2.f1);
	}


	for (ii e : edge)
	{
		adj[c].erase(e);
		adj[e.f1].erase({c, e.s2});
		rc(e.f1);
	}
}

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]].insert({H[i][1], L[i]});
		adj[H[i][1]].insert({H[i][0], L[i]});
	}

	ans = n;

	rc(0);
	return ans == n ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'void rc(int)':
race.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int i = 1; i < vec.size(); ++i)
      |                   ~~^~~~~~~~~~~~

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