Submission #421645

#	Time	Username	Problem	Language	Result	Execution time	Memory
421645		SuhaibSawalha1	Dreaming (IOI13_dreaming)	C++17	0 / 100	64 ms	9024 KiB

dreaming

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

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

int bfs (int u, bool f) {
	queue<array<int, 3>> q {{{u, 0}}};
	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[1];
}

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<int> cmp;
	for (int i = 0; i < N; ++i) {
		if (!dist[i]) {
			int a = bfs(i, 0);
			nodes.clear();
			bfs(bfs(a, 1), 1);
			int mn = 2e9;
			for (int u : nodes) {
				mn = min(mn, dist[u]);
			}
			cmp.push_back(mn);
		}
	}
	sort(cmp.begin(), cmp.end());
	return cmp.size() == 1 ? cmp[0] : cmp[cmp.size() - 2] + cmp.back() + L;
}

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