Submission #764991

#	Time	Username	Problem	Language	Result	Execution time	Memory
764991		Sohsoh84	Dreaming (IOI13_dreaming)	C++17	100 / 100	114 ms	40264 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

bool vis[MAXN];
int n, m, l;
vector<pll> adj[MAXN];
ll dist[2][MAXN];
vector<int> C;

void dfs(int v, int p, int c, ll d) {
	dist[c][v] = d;
	vis[v] = true;
	C.push_back(v);

	for (auto [u, l] : adj[v])
		if (u != p)
			dfs(u, v, c, d + l);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N, m = M, l = L;
	for (int i = 0; i < m; i++) {
		A[i]++;
		B[i]++;
		adj[A[i]].push_back({B[i], T[i]});
		adj[B[i]].push_back({A[i], T[i]});
	}

	ll ans = 0;

	vector<ll> vec;
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		C.clear();
		dfs(i, 0, 0, 0);
		
		int v = i;
		for (int e : C)
			if (dist[0][e] > dist[0][v])
				v = e;


		C.clear();
		dfs(v, 0, 1, 0);
		int u = i;
		for (int e : C)
			if (dist[1][e] > dist[1][u])
				u = e;
		ans = max(ans, dist[1][u]);

		C.clear();
		dfs(u, 0, 0, 0);

		int c = u;
		for (int e : C)
			if (max(dist[0][e], dist[1][e]) < max(dist[0][c], dist[1][c]))
				c = e;

		vec.push_back(max(dist[0][c], dist[1][c]));
	}
	
	sort(vec.begin(), vec.end());
	while (int(vec.size() > 1)) {
		ll x = vec.back();
		vec.pop_back();
		ll y = vec.back();
		vec.pop_back();

		ans = max(ans, x + y + L);
		vec.push_back(max(x, y + 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