Submission #640205

#	Time	Username	Problem	Language	Result	Execution time	Memory
640205		ymm	꿈 (IOI13_dreaming)	C++17	100 / 100	66 ms	15560 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --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;
int par[N], parw[N];
vector<pii> A[N];

pii dfs(int v, int p, int w)
{
	par[v] = p;
	parw[v] = w;
	pii ans = {0, v};
	for (auto [u, w] : A[v]) {
		if (u != p) {
			auto tmp = dfs(u, v, w);
			tmp.first += w;
			ans = max(ans, tmp);
		}
	}
	return ans;
}

int travelTime(int N, int M, int L, int V[], int U[], int T[])
{
	Loop (i,0,M) {
		A[V[i]].emplace_back(U[i], T[i]);
		A[U[i]].emplace_back(V[i], T[i]);
	}
	fill(par, par+N, -2);
	int ans = 0;
	vector<int> vec;
	Loop (v,0,N) {
		if (par[v] != -2)
			continue;
		int dard = dfs(v, -1, 0).second;
		auto [x, u] = dfs(dard, -1, 0);
		int y = 0;
		ans = max(ans, x);
		int kooft = 2e9;
		for (;;) {
			kooft = min(kooft, max(x, y));
			if (par[u] == -1)
				break;
			y += parw[u];
			x -= parw[u];
			u = par[u];
		}
		vec.push_back(kooft);
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	if (vec.size() >= 2)
		ans = max(ans, L + vec[0] + vec[1]);
	if (vec.size() >= 3)
		ans = max(ans, L + L + vec[1] + vec[2]);
	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