Submission #1209256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209256		vache_kocharyan	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

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

using namespace std;

vector<vector<pair<int, int>>>G;
int answ = 1e9 + 7, compSize, maxDep, maxMaxDep;
const int NN = 2e5 + 5;
map<int, int>depth, cur_depth;
bool used[NN];
int sz[NN];
int k;

void dfs(int node, int parent)
{
	sz[node] = 1;
	for (auto i : G[node])
	{
		if (i.first == parent || used[i.first])
			continue;
		dfs(i.first, node);
		sz[node] += sz[i.first];
	}
}

int find_centroid(int node, int parent)
{
	for (auto i : G[node])
	{
		if (i.first == parent || used[i.first])
			continue;
		if (sz[i.first] * 2 >= compSize)
			return find_centroid(i.first, node);
	}
	return node;
}

int centroid(int u)
{
	dfs(u, -1);
	compSize = sz[u];
	return find_centroid(u, -1);
}

void solve(int node, int parent, int node_depth, int node_sum)
{
	if (node_sum > k)return;
	if (cur_depth.count(node_sum))
		cur_depth[node_sum] = min(cur_depth[node_sum], node_depth);
	else
		cur_depth[node_sum] = node_depth;

	if (depth.count(k - node_sum))
		answ = min(answ, cur_depth[node_sum] + depth[k - node_sum]);

	for (auto i : G[node])
	{
		if (i.first == parent || used[i.first])
			continue;
		solve(i.first, node, node_depth + 1, node_sum + i.second);
		if (parent != -1)
			continue;
		for (auto &it : cur_depth)
		{
			if (!depth.count(it.first))
				depth[it.first] = it.second;
			else
				depth[it.first] = min(depth[it.first], it.second);
			it.second = 0;
		}
		for (auto j : cur_depth) {
			j.first = -1;
			j.second = -1;
		}
	}
}

void centroid_decomposition()
{
	queue<int>q;
	q.push(0);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();

		int c = centroid(u);
		solve(c, -1, 0, 0);
		for (auto i : depth) {
			i.first = -1;
			i.second = -1;	
		}
		used[c] = true;
		for (auto i : G[c])
		{
			if (used[i.first])
				continue;
			q.push(i.first);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	G.resize(N + 1);
	for (int i = 0; i < N - 1; i++)
	{
		G[H[i][0]].push_back({ H[i][1], L[i] });
		G[H[i][1]].push_back({ H[i][0], L[i] });
	}
	centroid_decomposition();
	if (answ == 1e9 + 7)
		return -1;
	return answ;
}

Compilation message (stderr)

race.cpp: In function 'void solve(int, int, int, int)':
race.cpp:73:33: error: assignment of read-only member 'std::pair<const int, int>::first'
   73 |                         j.first = -1;
      |                         ~~~~~~~~^~~~
race.cpp: In function 'void centroid_decomposition()':
race.cpp:91:33: error: assignment of read-only member 'std::pair<const int, int>::first'
   91 |                         i.first = -1;
      |                         ~~~~~~~~^~~~