Submission #718601

#	Time	Username	Problem	Language	Result	Execution time	Memory
718601		kunzaZa183	Race (IOI11_race)	C++17	21 / 100	3039 ms	21820 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dfs(int cur, int par, vector<vector<pair<int, int>>>& adjlist, vector<bool>& node, vector<int>& siz)
{
	siz[cur] = 1;
	for (auto a : adjlist[cur])
		if (a.first != par && node[a.first])
			siz[cur] += dfs(a.first, cur, adjlist, node, siz);
	return siz[cur];
}
int findcen(int cur, int par, vector<vector<pair<int, int>>>& adjlist, vector<bool>& node, vector<int>& siz, int n)
{
	int maxi = LLONG_MIN, maxid;
	for (auto a : adjlist[cur])
		if (a.first != par && node[a.first])
			if (siz[a.first] > maxi)
			{
				maxi = siz[a.first];
				maxid = a.first;
			}
	if (maxi <= n / 2)
		return cur;
	return findcen(maxid, cur, adjlist, node, siz, n);
}
int dfscen(int cur, int par, int dist, int depth, int head, map<int, vector<pair<int, int>>>& mii, vector<vector<pair<int, int>>>& adjlist, vector<bool>& node, vector<int>& siz)
{
	siz[cur] = 1;
	if (mii[dist].size() <= 1)
	{
		mii[dist].push_back({ depth, head });
		if (mii[dist].back().first < mii[dist].front().first)
			swap(mii[dist].back(), mii[dist].front());
	}
	else if (mii[dist].size() == 2)
	{
		if (depth < mii[dist].front().first)
		{
			swap(mii[dist].front(), mii[dist].back());
			mii[dist].front() = { depth, head };
		}
		else if (depth < mii[dist].back().first)
			mii[dist].back() = { depth, head };
	}
	for (auto a : adjlist[cur])
		if (a.first != par && node[a.first])
			siz[cur] += dfscen(a.first, cur, dist + a.second, depth + 1, head, mii, adjlist, node, siz);
	return siz[cur];
}
int anssubtree(int root, vector<vector<pair<int, int>>>& adjlist, vector<bool>& node, int n, int k)
{
	vector<int> siz(adjlist.size());
	dfs(root, root, adjlist, node, siz);
	int centroid = findcen(root, root, adjlist, node, siz, n);
	map<int, vector<pair<int, int>>> mii; /*length vector<depth, subtree>*/
	for (auto a : adjlist[centroid])
		dfscen(a.first, centroid, a.second, 1, a.first, mii, adjlist, node, siz);
	int shortest = LLONG_MAX;
	for (auto a : mii)
		for (auto b : a.second)           // O(1)
			for (auto c : mii[k - a.first]) // O(1)
				if (b.second != c.second)
					shortest = min(shortest, b.first + c.first);
	node[centroid] = 0;
	for (auto a : adjlist[centroid])
		if (node[a.first])
			shortest = min(shortest, anssubtree(a.first, adjlist, node, siz[a.first], k));
	return shortest;
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
	vector<vector<pair<int, int>>> adjlist(N);
	for (int i = 0; i < N - 1; i++)
		adjlist[H[i][0]].push_back({ H[i][1], L[i] }), adjlist[H[i][1]].push_back({ H[i][0], L[i] });
	vector<bool> vb(N, 1);
	int x=anssubtree(0, adjlist, vb, N, K);
	if (x == LLONG_MAX)
		x = -1;
	return x;
}

Compilation message (stderr)

race.cpp: In function 'long long int findcen(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<bool>&, std::vector<long long int>&, long long int)':
race.cpp:15:24: warning: 'maxid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 |  int maxi = LLONG_MIN, maxid;
      |                        ^~~~~

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