#include "dreaming.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 100008
const int inf = 1e9 + 7;
using namespace std;
typedef pair<int, int> pii;
pii operator+(pii x, int y){
return (x.fi <= y) ? make_pair(y, x.fi) : ((x.se < y) ? make_pair(x.fi, y) : x);
}
pii operator+(pii x, pii y){
return (x + y.fi) + y.se;
}
vector<pii>vt, l[nmax];
bool kt[nmax], vis[nmax];
int n, d = 0, ans = inf, diameter = 0, dis[2][nmax];
stack<int>s;
int a[nmax];
pii pf[nmax], sf[nmax];
void bfs(int root, int id){
fill(dis[id], dis[id] + nmax, -1);
s.push(root);
dis[id][root] = 0;
while (!s.empty()){
int u = s.top();
s.pop();
kt[u] = vis[u] = true;
for (pii it : l[u])
if (dis[id][it.fi] == -1){
dis[id][it.fi] = dis[id][u] + it.se;
s.push(it.fi);
}
}
}
int calc(int rt){
fill(kt, kt + n + 1, false);
bfs(rt, 0);
int u = 0, v = 0, res = inf;
for (int i = 1; i < n; i++)
if (dis[0][u] < dis[0][i])
u = i;
bfs(u, 1);
for (int i = 1; i < n; i++)
if (dis[1][v] < dis[1][i])
v = i;
bfs(v, 0);
for (int i = 0; i < n; i++)
if (kt[i])
res = min(res, max(dis[0][i], dis[1][i]));
diameter = max(diameter, dis[0][u]);
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
for (int i = 0; i < M; i++){
int u = A[i], v = B[i], w = T[i];
l[u].push_back({v, w});
l[v].push_back({u, w});
}
// assert(M == N - 2);
fill(vis, vis + n + 1, false);
pf[0] = {-inf, -inf};
for (int i = 0; i < N; i++)
if (!vis[i]){
a[++d] = calc(i);
pf[d] = pf[d - 1] + a[d];
}
sf[d + 1] = {-inf, -inf};
for (int i = d; i > 0; i--)
sf[i] = sf[i + 1] + a[i];
if (M == N - 2)
return max(ans, a[0] + a[1] + L);
for (int i = 1; i <= d; i++){
pii cur = pf[i - 1] + sf[i + 1];
ans = min(ans, max({diameter, cur.fi + cur.se + L * 2, cur.fi + a[i] + L}));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
8088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
8088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1057 ms |
6600 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
8088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
