Submission #961936

#	Time	Username	Problem	Language	Result	Execution time	Memory
961936		raspy	Race (IOI11_race)	C++14	0 / 100	2 ms	9816 KiB

race

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

using namespace std;

vector<pair<int, int>> graf[200005];
unordered_map<int, int> mp;
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(int u, int tr, int gl, int p, bool polni)
{
	if (tr > k)
		return;
	if (polni)
	{
		if (mp.find(tr) == mp.end())
			mp[tr] = gl;
		else
			mp[tr] = min(mp[tr], gl);
	}
	else
	{
		if (mp.find(k-tr) != mp.end())
			rez = min((rez == -1 ? gl+mp[k-tr] : rez), gl+mp[k-tr]);
	}
	for (auto [v, w] : graf[u])
	{
		if (rmv[v] || v == p)
			continue;
		dfs(v, tr+w, gl+1, u, polni);
	}
}

void decom(int u)
{
	int ct = gct(u, sbsz(u, -1), -1);
	mp.clear();
	rmv[ct] = 1;
	mp[0] = 0;
	for (auto [v, w] : graf[ct])
	{
		if (rmv[v])
			continue;
		dfs(v, w, 1, u, false);
		dfs(v, w, 1, u, true);
	}
	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:18:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'int gct(int, int, int)':
race.cpp:29:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void dfs(int, int, int, int, bool)':
race.cpp:55:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void decom(int)':
race.cpp:69:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |  for (auto [v, w] : graf[ct])
      |            ^
race.cpp:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |  for (auto [v, w] : graf[ct])
      |            ^

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