제출 #962425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962425		raspy	경주 (Race) (IOI11_race)	C++14	0 / 100	3 ms	10392 KiB

race

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

using namespace std;
typedef long long ll;

vector<pair<ll, ll>> graf[200005];
unordered_map<ll, ll> mp;
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.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(ll u)
{
	ll 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[])
{
	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});
	}
	mp.clear();
	decom(0);
	return rez;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'll sbsz(ll, ll)':
race.cpp:19:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'll gct(ll, ll, ll)':
race.cpp:30:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void dfs(ll, ll, ll, ll, bool)':
race.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void decom(ll)':
race.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for (auto [v, w] : graf[ct])
      |            ^
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