Submission #964773

#	Time	Username	Problem	Language	Result	Execution time	Memory
964773		raspy	Dreaming (IOI13_dreaming)	C++14	100 / 100	100 ms	24900 KiB

dreaming

#include "dreaming.h"

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define inf 1000000000

using namespace std;
typedef long long ll;

vector<pair<ll, ll>> graf[200005];
ll ob[200005];
ll mx[200005];
ll mx1[200005];
ll ixm[200005];
ll rez = 0;

ll dfs(ll u, ll p = -1)
{
	ob[u] = 1;
	ll ix = 0;
	for (auto [v, w] : graf[u])
	{
		if (v != p)
		{
			ll tr = dfs(v, u)+w;
			if (tr > mx[u])
			{
				mx1[u] = max(mx1[u], mx[u]);
				mx[u] = tr;
				ixm[u] = ix;
			}
			else
				mx1[u] = max(mx1[u], tr);
		}
		ix++;
	}
	return mx[u];
}

ll getBest(ll u, ll trd, ll p = -1)
{
	ll tr = max(trd, mx[u]);
	rez = max(rez, mx[u]+max(trd, mx1[u]));
	for (int i = 0; i < graf[u].size(); i++)
	{
		if (graf[u][i].first == p)
			continue;
		if (i == ixm[u])
		{
			tr = min(tr, getBest(graf[u][i].first, max(trd, mx1[u])+graf[u][i].second, u));
			continue;
		}
		tr = min(tr, getBest(graf[u][i].first, max(trd, mx[u])+graf[u][i].second, u));
	}
	return tr;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
	memset(ixm, -1, sizeof(ixm));
	for (ll i = 0; i < m; i++)
	{
		graf[a[i]].push_back({b[i], t[i]});
		graf[b[i]].push_back({a[i], t[i]});
	}
	priority_queue<ll> pq;
	for (ll i = 0; i < n; i++)
		if (!ob[i])
		{
			dfs(i);
			ll tr = getBest(i, 0);
			pq.push(tr);
		}
	ll tr = pq.top();
	pq.pop();
	if (pq.size())
		tr += pq.top()+l;
	rez = max(rez, tr);
	if (pq.size() > 1)
	{
		tr = pq.top();
		pq.pop();
		tr += pq.top();
		tr += 2*l;
		rez = max(rez, tr);
	}
	return rez;
}

Compilation message (stderr)

dreaming.cpp: In function 'll dfs(ll, ll)':
dreaming.cpp:24:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for (auto [v, w] : graf[u])
      |            ^
dreaming.cpp: In function 'll getBest(ll, ll, ll)':
dreaming.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < graf[u].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23