| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1184497 | lance0 | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
long long travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<vector<long long>>> graph(N);
for (int i = 0; i < M; i++) {
int x,y,z; x = A[i]; y = B[i]; z = T[i];
graph[x].push_back({y,z});
graph[y].push_back({x,z});
}
vector<long long> radius;
vector<long long> diameter;
bool vis1[N] = {}, vis2[N] = {};
int vis3[N] = {};
for (int i = 0; i < N; i++) {
if (!vis1[i]) {
queue<pair<long long, long long>> bfs;
for (int j = 0; j < graph[i].size(); j++) {
bfs.push(make_pair(graph[i][j][0], graph[i][j][1]));
}
vis1[i] = true;
long long start = 0, weight = 0;
while (!bfs.empty()) {
long long x = bfs.front().first;
long long y = bfs.front().second;
if (y > weight) {
start = x;
weight = y;
}
for (int j = 0; j < graph[x].size(); j++) {
if (vis1[j] == false) {
bfs.push(make_pair(graph[x][j][0], graph[x][j][1]));
}
}
vis1[x] = true;
}
for (int j = 0; j < graph[start].size(); j++) {
bfs.push(make_pair(graph[start][j][0], graph[start][j][1]));
}
vis2[start] = true;
long long end = 0; weight = 0;
while (!bfs.empty()) {
long long x = bfs.front().first;
long long y = bfs.front().second;
if (y > weight) {
end = x;
weight = y;
}
for (int j = 0; j < graph[x].size(); j++) {
if (vis2[j] == false) {
bfs.push(make_pair(graph[x][j][0], graph[x][j][1]));
}
}
vis2[x] = true;
}
diameter.push_back(weight);
long long rad = weight;
stack<long long> dfs;
dfs.push(start);
while (!dfs.empty()) {
long long x = dfs.top();
if (x == end) {
long long curr = 0;
while (!dfs.empty()) {
dfs.pop();
long long y = dfs.top();
for (int j = 0; j < graph[x].size(); j++) {
if (graph[x][j][0] == y) {
curr += graph[x][j][1];
rad = min(rad,max(curr,weight-curr));
break;
}
}
x = y;
}
} else if (vis3[x] == graph[x].size()) {
dfs.pop();
} else {
dfs.push(graph[x][vis3[x]][0]);
vis3[x]++;
}
}
}
}
while (radius.size() < 3) {
radius.push_back(0); //makes sure you can't OOB the radius
}
sort(radius.begin(), radius.end(), greater<int>());
sort(diameter.begin(),diameter.end(), greater<int>());
return max({radius[0]+radius[1]+L, radius[1]+radius[2]+L+L, diameter[0]});
}