// a) ans = max(diametri)
// b) max "code", dove coda = min(max distanza da un nodo)
// if 1 componente: return ans
// ans = max(ans, codaMax[0] + codaMax[1] + L)
// if 2 componenti: return ans
// ans = max(ans, codaMax[1] + codaMax[2] + 2*L)
// return ans
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
vector<vector<int>> c;
vector<vector<pair<int, int>>> g;
vector<int> cmp;
int gty = 0;
array<int, 2> dmax;
vector<int> d, p, vis;
void dfs1(int v) {
cmp[v] = gty;
c.back().push_back(v);
for (int i = 0; i < g[v].size(); ++i)
if (cmp[g[v][i].first] != gty)
dfs1(g[v][i].first);
}
void dfs(int v, int ty) {
vis[v] = ty;
if (d[v] > dmax[1])
dmax = {v, d[v]};
for (int i = 0; i < g[v].size(); ++i) {
int u = g[v][i].first;
int w = g[v][i].second;
if (vis[u] != ty) {
d[u] = d[v] + w;
dfs(u, ty);
}
}
}
int diam(int v) {
dmax = {v, 0}; dfs(v, gty++);
v = dmax[0]; d[v] = 0;
dfs(v, gty++);
return dmax[1];
}
int coda(int v) {
// cout << "coda[" << v << "] = ";
// modo stupido O(n^2)
int ans = 1e9;
for (int u : c[cmp[v]]) {
fill(d.begin(), d.end(), 0);
dfs(u, gty++);
ans = min(ans, *max_element(d.begin(), d.end()));
}
// cout << ans << "\n";
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.resize(N);
d.resize(N);
p.resize(N, -1);
vis.resize(N, -1);
cmp.resize(N, -1);
for (int i = 0; i < M; ++i) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < N; ++i) {
if (cmp[i] == -1) {
c.push_back(vector<int>(0));
dfs1(i);
++gty;
}
}
int kek = gty;
int ans = 0;
for (int i = 0; i < kek; ++i)
ans = max(ans, diam(c[i][0]));
array<int, 3> o{};
for (int i = 0; i < kek; ++i) {
o[2] = max(o[2], coda(c[i][0]));
if (o[1] < o[2]) swap(o[1], o[2]);
if (o[0] < o[1]) swap(o[0], o[1]);
}
// cout << o[0] << " " << o[1] << " " << o[2] << "\n";
if (gty == 1) return ans;
ans = max(ans, o[0] + o[1] + L);
if (gty == 2) return ans;
ans = max(ans, o[1] + o[2] + 2*L);
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < g[v].size(); ++i)
| ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i = 0; i < g[v].size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
12504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
12504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
9732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
12504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
