Submission #1262052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262052		ciao_gio	Dreaming (IOI13_dreaming)	C++20	47 / 100	66 ms	9204 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

using namespace std;

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	vector<vector<array<int, 2>>> adj(N);
	for (int i = 0; i < M; i++) {
		adj[A[i]].push_back({B[i], T[i]});
		adj[B[i]].push_back({A[i], T[i]});
	}

	vector<int> d0(N, 1e9), d1(N, 1e9), d2(N, 1e9);
	vector<bool> v0(N, false), v1(N, false), v2(N, false), vf(N, false);

	auto dijkstra = [N, &adj] (int i, vector<int> &distance, vector<bool> &visited) -> int {
		priority_queue<array<int, 2>> q;
		q.push({0, i}); distance[i] = 0;

		int x = i;

		while (!q.empty()) {
			auto [_, v] = q.top(); q.pop();

			if (visited[v]) continue;
			if (distance[v] > distance[x]) x = v;
			visited[v] = true;

			for (auto [u, w]: adj[v]) {
				if (distance[v] + w < distance[u]) {
					distance[u] = distance[v] + w;
					q.push({-distance[u], u});
				}
			}
		}

		return x;
	};

	auto find_center = [N, &adj, &d1, &d2, &vf] (int i) -> int {
		queue<int> q;
		vf[i] = true; q.push(i);

		int x = i;

		while(!q.empty()) {
			int v = q.front(); q.pop();
			for (auto [u, _]: adj[v]) {
				if (vf[u]) continue;
				if (max(d1[u], d2[u]) < max(d1[x], d2[x])) x = u;
				vf[u] = true;
				q.push(u);
			}
		}

		return x;
	};

	int res = 0;
	int e1 = 0, e2 = 0;

	for (int i = 0; i < N; i++) {
		if (vf[i]) continue;

		int a = dijkstra(i, d0, v0);
		int b = dijkstra(a, d1, v1);
		
		dijkstra(b, d2, v2);

		res = max(res, d1[b]);
		
		int c = find_center(i);
		int e = max(d1[c], d2[c]);

		if (e > e1) {
			e2 = e1;
			e1 = e;
		}
		else if (e > e2) {
			e2 = e;
		}
	}

	res = max(res, e1 + e2 + L);

	return res;
}

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