Submission #491996

#	Time	Username	Problem	Language	Result	Execution time	Memory
491996		franfill	Dreaming (IOI13_dreaming)	C++17	18 / 100	42 ms	12356 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
typedef pair < ll , ll > pll;

vector < vector < pll > > g;
vector < bool > vis;
vector < pll > b;
ll d = 0;

ll dfs1(int x, int pa=-1)
{
	vis[x] = true;
	b[x] = {0, 0};
	for (auto [y, w] : g[x]) if (y != pa)
	{
		ll temp = dfs1(y, x) + w;
		if (b[x].second < temp) b[x].second = temp;
		if (b[x].first < b[x].second) swap(b[x].first, b[x].second); 
	}
	return b[x].first;
}

ll dfs2(int x, ll w = 0, int pa=-1)
{
	if (pa != -1)
	{
		ll up = b[pa].first;
		if (up == b[x].first + w) up = b[pa].second;
		up += w;

		if (up > b[x].second) b[x].second = up;
		if (b[x].second > b[x].first) swap(b[x].second, b[x].first);
	}
	ll bes = b[x].first;
	d = max(d, b[x].first + b[x].second);
	for (auto [y, w] : g[x]) if (y != pa)
	{
		bes = min(bes, dfs2(y, w, x));
	}
	return bes;
}

ll calc(int x)
{
	dfs1(x);
	return dfs2(x);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
	g.resize(N);	
	vis.resize(N, false);
	b.resize(N, {0, 0});
	for (int i = 0; i < M; i++)
	{
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}
	ll g1=-1, g2=-1, g3=-1;
	for (int x = 0; x < N; x++) if (!vis[x])
	{
		ll temp = calc(x);
		if (temp > g1)
		{
			g3 = g2;
			g2 = g1;
			g1 = temp;
		}
		else if (temp > g2)
		{
			g3 = g2;
			g2 = temp;
		}
		else if (temp > g3)
		{
			g3 = temp;
		}
	}
	if (g2 == -1)
	{
		return d;
	}
	if (g3 == -1)
	{
		return g1 + g2 + L;
	}
	ll ans = g1 + g2 + L;
	ans = max(ans, g2 + g3 + L + L);
	return ans;
}

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