Submission #421714

#	Time	Username	Problem	Language	Result	Execution time	Memory
421714		SuhaibSawalha1	꿈 (IOI13_dreaming)	C++17	100 / 100	138 ms	10712 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> adj;
vector<int> dist, nodes;
int n;

array<int, 2> bfs (int u, bool f) {
	queue<array<int, 3>> q {{{u, 0, -1}}};
	array<int, 2> MX {0, u};
	int v = 0;
	while (q.size()) {
		++v;
		u = q.front()[0];
		int d = q.front()[1];
		int p = q.front()[2];
		q.pop();
		if (f) {
			nodes.push_back(u);
			dist[u] = max(dist[u], d);
		}
		MX = max(MX, {d, u});
		for (auto &v : adj[u]) {
			if (v[0] != p) {
				q.push({v[0], d + v[1], u});
			}
		}
	}
	return MX;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
	adj.resize(N);
	dist.resize(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<array<int, 2>> cmp;
	for (int i = 0; i < N; ++i) {
		if (!dist[i]) {
			int a = bfs(i, 0)[1];
			nodes.clear();
			bfs(bfs(a, 1)[1], 1);
			array<int, 2> mn = {(int)2e9, (int)2e9};
			for (int u : nodes) {
				mn = min(mn, {dist[u], u});
			}
			cmp.push_back(mn);
		}
	}
	int mx = (*max_element(cmp.begin(), cmp.end()))[1];
	for (auto &e : cmp) {
		if (e[1] != mx) {
			adj[e[1]].push_back({mx, L});
			adj[mx].push_back({e[1], L});
		}
	}
	return bfs(bfs(0, 0)[1], 0)[0];
}

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