Submission #763991

#	Time	Username	Problem	Language	Result	Execution time	Memory
763991		ymm	Dreaming (IOI13_dreaming)	C++17	100 / 100	75 ms	19756 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;

const int N = 100'010;
vector<pll> A[N];
bool vis[N];
int par[N];
ll dis[N];

void dfs_vis(int v)
{
	vis[v] = 1;
	for (auto [u, _] : A[v]) {
		if (!vis[u])
			dfs_vis(u);
	}
}


pll dfs_farthest(int v, int p, ll h)
{
	pll ans = {h, v};
	par[v] = p;
	dis[v] = h;
	for (auto [u, w] : A[v]) {
		if (u != p)
			ans = max(ans, dfs_farthest(u, v, h+w));
	}
	return ans;
}

int travelTime(int n, int m, int L, int V[], int U[], int W[])
{
	Loop (i,0,m) {
		int v = V[i], u = U[i], w = W[i];
		A[v].push_back({u,w});
		A[u].push_back({v,w});
	}
	vector<ll> vec;
	ll ans = 0;
	Loop (v,0,n) {
		if (vis[v])
			continue;
		dfs_vis(v);
		int u = dfs_farthest(v, -1, 0).second;
		u = dfs_farthest(u, -1, 0).second;
		ll rad = LONG_LONG_MAX;
		ll dia = dis[u];
		ans = max(ans, dia);
		while (u != -1) {
			rad = min(rad, max(dis[u], dia-dis[u]));
			u = par[u];
		}
		vec.push_back(rad);
	}
	sort(vec.begin(), vec.end());
	if (vec.size() >= 2)
		ans = max(ans, vec.end()[-1] + vec.end()[-2] + L);
	if (vec.size() >= 3)
		ans = max(ans, vec.end()[-2] + vec.end()[-3] + L + L);
	return ans;
}

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