# include "dreaming.h"
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int fix[N];
vector < int > pts;
vector < pair < int , int > > edges[N];
void dfs(int x, int p, vector < int > &dist){
fix[x] = 1;
pts.push_back(x);
for(int i = 0; i < edges[x].size(); i ++){
if(edges[x][i].first != p){
dfs(edges[x][i].first, x, dist);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
vector < int > dist_a(N), dist_b(N), cen;
for(int i = 0; i < M; i ++){
edges[A[i]].push_back(make_pair(B[i], T[i]));
edges[B[i]].push_back(make_pair(A[i], T[i]));
}
for(int i = 0; i < N; i ++){
if(fix[i] != 1){
pts.clear();
dfs(i, 0, dist_a);
int a = pts[0];
for(int i = 0; i < pts.size(); i ++){
if(dist_a[pts[i]] < dist_a[a]) a = pts[i];
}
pts.clear();
dfs(a, 0, dist_a);
int b = pts[0];
for(int i = 0; i < pts.size(); i ++){
if(dist_a[pts[i]] < dist_a[b]) b = pts[i];
}
if(M == N - 1) return dist_a[b];
pts.clear();
dfs(b, 0, dist_b);
int res = 1e9;
for(int i = 0; i < pts.size(); i ++){
res = min(res, max(dist_a[pts[i]], dist_b[pts[i]]));
}
cen.push_back(res);
pts.clear();
}
}
if(cen.size() == 1) return cen.back();
else{
sort(cen.rbegin(), cen.rend());
int res = 0;
if(cen.size() >= 2) res = cen[0] + cen[1] + L;
if(cen.size() >= 3) res = max(res, cen[1] + cen[2] + 2 * L);
return res;
}
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int, std::vector<int>&)':
dreaming.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < edges[x].size(); i ++){
~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pts.size(); i ++){
~~^~~~~~~~~~~~
dreaming.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pts.size(); i ++){
~~^~~~~~~~~~~~
dreaming.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pts.size(); i ++){
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
14204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
14204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
14204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
9336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
14204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
14204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
