Submission #962441

#	Time	Username	Problem	Language	Result	Execution time	Memory
962441		raspy	Race (IOI11_race)	C++14	100 / 100	499 ms	51744 KiB

race

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

using namespace std;
typedef long long ll;

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

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

ll gct(ll u, ll vel, ll 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(ll u, ll tr, ll gl, ll p, bool polni)
{
	if (tr > k)
		return;
	if (polni)
	{
		if (mp[tr] == -1)
			mp[tr] = gl;
		else
			mp[tr] = min(mp[tr], gl);
	}
	else
	{
		if (mp[k-tr] != -1)
			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 del(int tr, int u, int p = -1)
{
	if(tr > k) return;
	mp[tr] = -1;
	for(auto [v, w]: graf[u])
		if(v != p && !rmv[v])
			del(tr + w, v, u);
}

void decom(ll u)
{
	u = gct(u, sbsz(u, -1), -1);
	rmv[u] = 1;
	mp[0] = 0;
	for (auto [v, w] : graf[u])
	{
		if (rmv[v])
			continue;
		dfs(v, w, 1, u, false);
		dfs(v, w, 1, u, true);
	}
	for(auto [v, w]: graf[u])
		if(!rmv[v])
			del(w, v);
	for (auto [v, w] : graf[u])
		if (!rmv[v])
			decom(v);
	return;
}

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

Compilation message (stderr)

race.cpp: In function 'll sbsz(ll, ll)':
race.cpp:20:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'll gct(ll, ll, ll)':
race.cpp:31:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void dfs(ll, ll, ll, ll, bool)':
race.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void del(int, int, int)':
race.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |  for(auto [v, w]: graf[u])
      |           ^
race.cpp: In function 'void decom(ll)':
race.cpp:79:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp:86:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |  for(auto [v, w]: graf[u])
      |           ^
race.cpp:89:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |  for (auto [v, w] : graf[u])
      |            ^

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