#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "dreaming.h"
using namespace std;
const int inf = 7 + 1e9;
vector <int> vis, f, g;
vector <vector <II>> adj;
vector <vector <int>> a;
int dfs(int u) {
int ans = 0;
vis[u] = 1;
for (auto z : adj[u]) {
int v = z.st, w = z.nd;
if (vis[v])
continue;
ans = max(ans, dfs(v));
f[u] = max(f[u], f[v] + w);
for (int i = 0; i < 2; i ++)
if (a[v][i] + w > a[u][0]) {
a[u][1] = a[u][0];
a[u][0] = a[v][i] + w;
}
else if (a[v][i] + w > a[u][1])
a[u][1] = a[v][i] + w;
}
return max(ans, a[u][0] + a[u][1]);
}
int dfs_(int u, int p) {
int ans = max(f[u], g[u]);
vector <II> V;
for (auto z : adj[u])
if (z.st != p)
V.push_back(z);
vector <int> l(V.size(), 0), r(V.size(), 0);
for (int i = 1; i < V.size(); i ++)
l[i] = max(l[i - 1], f[V[i - 1].st] + V[i - 1].nd);
for (int i = (int)V.size() - 2; i >= 0; i --)
r[i] = max(r[i + 1], f[V[i + 1].st] + V[i + 1].nd);
for (int i = 0; i < V.size(); i ++) {
int v = V[i].st, w = V[i].nd;
g[v] = max({l[i], r[i], g[u]}) + w;
ans = min(ans, dfs_(v, u));
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.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]});
}
vis.assign(N, 0);
f.assign(N, 0);
g.assign(N, 0);
a.assign(N, vector <int> (2, 0));
vector <int> c;
int ma = 0;
for (int i = 0; i < N; i ++)
if (!vis[i]) {
ma = max(ma, dfs(i));
int val = dfs_(i, 0);
c.push_back(val);
}
if (c.size() == 1)
return c[0];
if (c.size() == 2)
return c[0] + c[1] + L;
vector <vector <int>> l(c.size(), vector <int> (2, 0)), r(c.size(), vector <int> (2, 0));
for (int i = 1; i < c.size(); i ++) {
l[i][0] = l[i - 1][0];
l[i][1] = l[i - 1][1];
if (c[i - 1] > l[i][0]) {
l[i][1] = l[i][0];
l[i][0] = c[i - 1];
}
else if (c[i - 1] > l[i][1])
l[i][1] = c[i - 1];
}
for (int i = (int)c.size() - 2; i >= 0; i --) {
r[i][0] = r[i + 1][0];
r[i][1] = r[i + 1][1];
if (c[i + 1] > r[i][0]) {
r[i][1] = r[i][0];
r[i][0] = c[i + 1];
}
else if (c[i + 1] > r[i][1])
r[i][1] = c[i + 1];
}
int ans = inf;
for (int i = 0; i < c.size(); i ++) {
int ma1 = l[i][0], ma2 = l[i][1];
for (int j = 0; j < 2; j ++)
if (r[i][j] > ma1) {
ma2 = ma1;
ma1 = r[i][j];
}
else if (r[i][j] > ma2)
ma2 = r[i][j];
ans = min(ans, max(ma1 + c[i] + L, ma1 + ma2 + 2 * L));
}
return max(ans, ma);
}
Compilation message
dreaming.cpp: In function 'int dfs_(int, int)':
dreaming.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 1; i < V.size(); i ++)
| ~~^~~~~~~~~~
dreaming.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < V.size(); i ++) {
| ~~^~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 1; i < c.size(); i ++) {
| ~~^~~~~~~~~~
dreaming.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i = 0; i < c.size(); i ++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
26704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
26704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
18192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
26704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
