Submission #231799

#	Time	Username	Problem	Language	Result	Execution time	Memory
231799		peijar	Race (IOI11_race)	C++17	100 / 100	600 ms	34408 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define SZ(v) ((int)(v).size())

using ll = long long;

const int MAXN = 2e5;
int ans;
vector<pair<int, int>> G[MAXN];
int sz[MAXN];
int target;
int sz_above[MAXN];
int par[MAXN];
queue<int> q;
bool blocked[MAXN];

struct Path
{
	int len, val;
};

vector<Path> paths;
const int MAX = 1e6+1;
int have[MAX];

void dfs(int u)
{
	sz[u] = 1;
	for (auto [v, w] : G[u])
		if (!blocked[v] and v != par[u])
		{
			par[v] = u;
			dfs(v);
			sz[u] += sz[v];
		}
}

int get_centroid(int source)
{
	int centroid = source;
	int bst = sz[source];
	sz_above[source] = 0;
	q.push(source);
	while (SZ(q))
	{
		int u = q.front(); q.pop();

		int cur_sz = sz_above[u];
		for (auto [v, w] : G[u])
			if (!blocked[v] and v != par[u])
			{
				cur_sz = max(cur_sz, sz[v]);
				sz_above[v] = sz_above[u] + sz[u] - sz[v];
				q.push(v);
			}
		if (cur_sz < bst)
			bst = cur_sz, centroid = u;
	}
	return centroid;
}

void dfs2(int u, int p, int depth, int cur_weight)
{
	if (cur_weight > target)
		return ;
	paths.push_back({depth, cur_weight});
	for (auto [v, w] : G[u])
		if (v != p and !blocked[v])
			dfs2(v, u, depth + 1, cur_weight + w);
}

void run_centroid(int source)
{
	par[source] = -1;
	dfs(source);
	vector<int> to_reset;

	int centroid = get_centroid(source);
	have[0] = 0;
	for (auto [v, w] : G[centroid])
		if (!blocked[v])
		{
			dfs2(v, centroid, 1, w);
			for (auto [len, val] : paths)
				if (have[target - val] != -1)
					ans = min(ans, have[target - val] + len);
			for (auto [len, val] : paths)
			{
				if (have[val] != -1)
					have[val] = min(have[val], len);
				else
				{
					have[val] = len;
					to_reset.push_back(val);
				}
			}
			paths.clear();
		}
	for (auto v : to_reset)
		have[v] = -1;
	blocked[centroid] = true;
	for (auto [v, _] : G[centroid])
		if (!blocked[v])
			run_centroid(v);
}

int best_path(int nb_villes, int _target, int edges[][2], int lengths[])
{
	for (int i(0); i < MAX; ++i)
		have[i] = -1;
	target = _target;
	ans = 1e9;
	for (int i(0); i < nb_villes - 1; ++i)
	{
		G[edges[i][0]].emplace_back(edges[i][1], lengths[i]);
		G[edges[i][1]].emplace_back(edges[i][0], lengths[i]);
	}
	run_centroid(0);

	if (ans == 1e9)
		ans = -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int)':
race.cpp:30:17: warning: unused variable 'w' [-Wunused-variable]
  for (auto [v, w] : G[u])
                 ^
race.cpp: In function 'int get_centroid(int)':
race.cpp:50:18: warning: unused variable 'w' [-Wunused-variable]
   for (auto [v, w] : G[u])
                  ^
race.cpp: In function 'void run_centroid(int)':
race.cpp:103:17: warning: unused variable '_' [-Wunused-variable]
  for (auto [v, _] : G[centroid])
                 ^

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