#include "dreaming.h"
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair <ll, int>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
map <int, vector <pii>> adj;
map <int, vector <int>> cc;
map <pii, int> edges;
map <int, int> ccnum;
int maxgrp;
map <int, int> roots;
map <int, int> layer;
vector <int> mins;
ll m1 = -1, m2 = -1, m3 = -1;
for (int i = 0; i < M; i++)
{
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
edges[make_pair(A[i], B[i])] = T[i];
edges[make_pair(B[i], A[i])] = T[i];
}
int cur = 0;
for (int i = 0; i < N; i++)
{
ccnum[i] = -1;
}
for (int i = 0; i < N; i++)
{
if (ccnum[i] == -1)
{
queue <int> curs;
curs.push(i);
ccnum[i] = cur;
while (!curs.empty())
{
int a = curs.front();
curs.pop();
for (auto x : adj[a])
{
if (ccnum[x.first] == -1)
{
ccnum[x.first] = cur;
curs.push(x.first);
}
}
}
cur++;
}
}
for (int i = 0; i < N; i++)
{
cc[ccnum[i]].push_back(i);
layer[i] = -1;
}
maxgrp = cur - 1;
for (int i = 0; i <= maxgrp; i++)
{
if (cc[i].size() == 1)
{
if (m3 < 0)
{
m3 = 0;
if (m3 > m2)
{
swap(m3, m2);
if (m2 > m1)
{
swap(m2, m1);
}
}
}
continue;
}
bool path = true;
roots[i] = cc[i][0];
queue <pii> depth;
layer[roots[i]] = 0;
depth.push(make_pair(roots[i], 0));
map <int, vector <int>> layers;
layers[0].push_back(roots[i]);
int maxlayer = 0;
map <int, vector <int>> children;
map <int, int> parent;
map <int, pii> big;
for (int a : cc[i])
{
parent[a] = -1;
}
while (!depth.empty())
{
pii a = depth.front();
depth.pop();
for (pii b : adj[a.first])
{
if (layer[b.first] == -1)
{
depth.push(make_pair(b.first, a.second + 1));
layer[b.first] = a.second + 1;
layers[a.second + 1].push_back(b.first);
maxlayer = max(maxlayer, a.second + 1);
children[a.first].push_back(b.first);
if (children[a.first].size() > 2)
{
path = false;
}
parent[b.first] = a.first;
}
}
}
queue <int> calc;
map <int, bool> seen;
seen[-1] = true;
for (int a : cc[i])
{
if (children[a].size() == 0)
{
calc.push(a);
seen[a] = true;
}
}
while (!calc.empty())
{
int a = calc.front();
calc.pop();
if (!seen[parent[a]])
{
calc.push(parent[a]);
seen[parent[a]] = true;
}
if (children[a].size() == 0)
{
big[a] = make_pair(0, a);
continue;
}
pii x = make_pair(-1, -1);
for (int b : children[a])
{
int l1 = big[b].first;
if (l1 >= 0 && l1 + edges[make_pair(a, b)] > x.first)
{
x.first = l1 + edges[make_pair(a, b)];
x.second = big[b].second;
}
}
big[a] = x;
}
int start = -1;
int end = -1;
int common = -1;
ll length = 0;
ll tot = 0;
if (path)
{
start = roots[i];
int a = roots[i];
while (children[a].size() > 0)
{
length += edges[make_pair(a, children[a][0])];
a = children[a][0];
}
end = a;
}
else
{
for (int a : cc[i])
{
pii max1 = make_pair(0, 0);
pii max2 = make_pair(0, 0);
if (children[a].size() >= 2)
{
for (int b : children[a])
{
if (edges[make_pair(a, b)] + big[b].first > max2.first)
{
max2 = make_pair(edges[make_pair(a, b)] + big[b].first, big[b].second);
if (max2 > max1)
{
swap(max2, max1);
}
}
}
}
if (max1.first + max2.first > length)
{
length = max1.first + max2.first;
start = max1.second;
end = max2.second;
common = a;
}
}
}
int curpos;
if (path)
{
curpos = end;
}
else
{
curpos = start;
}
int minmax = 0;
while (tot * 2 < length)
{
tot += edges[make_pair(curpos, parent[curpos])];
if (tot * 2 == length)
{
minmax = tot;
}
if (tot * 2 > length)
{
if (tot * 2 - edges[make_pair(curpos, parent[curpos])] >= length)
{
minmax = length - tot + edges[make_pair(curpos, parent[curpos])];
}
else
{
minmax = tot;
}
}
curpos = parent[curpos];
}
if (m3 < minmax)
{
m3 = minmax;
if (m3 > m2)
{
swap(m3, m2);
if (m2 > m1)
{
swap(m2, m1);
}
}
}
}
if (m2 == -1)
{
return m1;
}
else if (m3 == -1)
{
return m1 + L + m2;
}
else
{
return max(m1 + L + m2, m2 + m3 + 2 * L);
}
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:155:7: warning: variable 'common' set but not used [-Wunused-but-set-variable]
155 | int common = -1;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
61984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
61984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
447 ms |
31348 KB |
Output is correct |
| 2 |
Correct |
388 ms |
31432 KB |
Output is correct |
| 3 |
Correct |
390 ms |
31352 KB |
Output is correct |
| 4 |
Correct |
398 ms |
31456 KB |
Output is correct |
| 5 |
Correct |
398 ms |
31336 KB |
Output is correct |
| 6 |
Correct |
426 ms |
33176 KB |
Output is correct |
| 7 |
Correct |
438 ms |
32848 KB |
Output is correct |
| 8 |
Correct |
370 ms |
30828 KB |
Output is correct |
| 9 |
Correct |
392 ms |
30576 KB |
Output is correct |
| 10 |
Correct |
486 ms |
32400 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
150 ms |
28408 KB |
Output is correct |
| 13 |
Correct |
139 ms |
28552 KB |
Output is correct |
| 14 |
Correct |
151 ms |
28500 KB |
Output is correct |
| 15 |
Correct |
139 ms |
28504 KB |
Output is correct |
| 16 |
Correct |
151 ms |
28480 KB |
Output is correct |
| 17 |
Correct |
148 ms |
28472 KB |
Output is correct |
| 18 |
Correct |
144 ms |
28484 KB |
Output is correct |
| 19 |
Correct |
141 ms |
28484 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
5 ms |
1100 KB |
Output is correct |
| 23 |
Correct |
157 ms |
28460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
61984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
