Submission #961920

#	Time	Username	Problem	Language	Result	Execution time	Memory
961920		raspy	Race (IOI11_race)	C++14	0 / 100	4 ms	9560 KiB

race

#include "race.h"
#include <unordered_map>
#include <vector>
#include <iostream>

using namespace std;

vector<pair<int, int>> graf[200005];
bool rmv[200005];
int sz[200005];
int rez = -1;
int k = 0;

int sbsz(int u, int p)
{
	sz[u] = 1;
	for (auto [v, w] : graf[u])
	{
		if (rmv[v] || v == p)
			continue;
		sz[u] += sbsz(v, u);
	}
	return sz[u];
}

int gct(int u, int vel, int p)
{
	for (auto [v, w] : graf[u])
	{
		if (rmv[v] || v == p)
			continue;
		if (sz[v]*2 > vel)
			return gct(v, vel, u);
	}
	return u;
}

void dfs(unordered_map<int, int>& mp, vector<pair<int, int>>& nv, int u, int tr, int gl, int p = -1)
{
	if (tr > k)
		return;
	// cout << "-> " << gl << " " << u << " " << tr << "\n";
	nv.push_back({tr, gl});
	if (mp.find(k-tr) != mp.end())
	{
		rez = min((rez == -1 ? gl + mp[k-tr] : rez), gl + mp[k-tr]);
		// cout << u << " " << tr << " " << gl << "\n";
	}
	for (auto [v, w] : graf[u])
	{
		if (rmv[v] || v == p)
			continue;
		dfs(mp, nv, v, tr+w, gl+1, u);
	}
}

void decom(int u)
{
	int ct = gct(u, sbsz(u, -1), -1);
	unordered_map<int, int> mp;
	mp[0] = 0;
	for (auto [v, w] : graf[ct])
	{
		if (rmv[v])
			continue;
		vector<pair<int, int>> nv;
		dfs(mp, nv, v, w, 1, u);
		for (auto [x, y] : nv)
		{
			if (mp.find(x) == mp.end())
				mp[x] = y;
			else
				mp[x] = min(mp[x], y);
		}
	}
	rmv[ct] = 1;
	for (auto [v, w] : graf[ct])
		if (!rmv[v])
			decom(v);
	return;
}

int best_path(int N, int K, int H[][2], int L[])
{
	int n = N;
	k = K;
	for (int i = 0; i < n-1; i++)
	{
		int u = H[i][0], v = H[i][1];
		int w = L[i];
		// cout << "--> " << u << " " << v << " " << w << "\n";
		graf[u].push_back({v, w});
		graf[v].push_back({u, w});
	}
	decom(0);
	return rez;
}

Compilation message (stderr)

race.cpp: In function 'int sbsz(int, int)':
race.cpp:17:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'int gct(int, int, int)':
race.cpp:28:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void dfs(std::unordered_map<int, int>&, std::vector<std::pair<int, int> >&, int, int, int, int)':
race.cpp:49:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void decom(int)':
race.cpp:62:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |  for (auto [v, w] : graf[ct])
      |            ^
race.cpp:68:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   for (auto [x, y] : nv)
      |             ^
race.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |  for (auto [v, w] : graf[ct])
      |            ^

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