#pragma GCC optimize("O3")
#include "dreaming.h"
#include <bits/stdc++.h>
const int INF = 2e9;
using namespace std;
struct arco
{
int to, p;
};
int N;
vector<vector<arco>> g;
vector<int> dist;
vector<pair<int, int>> centers;
vector<int> temp;
int bfs(int node, bool precalcolo){
vector<int> padre(N, -1);
queue<int> q;
dist[node] = 0;
q.push(node);
int maxiNode = node;
int maxi = 0;
while(!q.empty()){
auto curr = q.front();
q.pop();
if(maxi < dist[curr])
maxi = dist[curr], maxiNode = curr;
for(auto i : g[curr]){
if(dist[i.to] > dist[curr] + i.p){
padre[i.to] = curr;
q.push(i.to);
dist[i.to] = dist[curr] + i.p;
}
}
}
// for(auto i : padre)cout << i << " ";
// cout << "\n\n";
if(precalcolo)
temp.push_back(maxiNode);
else{
int diameter = maxi;
int center = maxiNode;
int curr = maxiNode;
maxi = maxi;
// cout << curr <<"\n";
// cout << "\t" << max(diameter-dist[curr], dist[curr]) << " " << maxi << "\n";
while(padre[curr] != -1){
//cout << curr << " " << padre[curr] << "\n";
curr = padre[curr];
//cout << curr << "\n";
if(max(diameter-dist[curr], dist[curr]) < maxi){
//cout << "\t" << max(diameter-dist[curr], dist[curr]) << " " << maxi << "\n";
maxi = max(diameter-dist[curr], dist[curr]);
center = curr;
}
}
centers.push_back({maxi, center});
}
return *max_element(dist.begin(), dist.end());
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
::N = N;
g.resize(N);
dist.resize(N);
centers.reserve(N);
temp.reserve(N);
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]});
}
fill(dist.begin(), dist.end(), INF);
for(int i=0; i<N; i++) if(dist[i] == INF)
bfs(i, true);
fill(dist.begin(), dist.end(), INF);
for(auto i : temp)
bfs(i, false);
int ans = 0;
sort(centers.begin(), centers.end());
for(int i=0; i<centers.size()-1; i++){
ans = max(ans, L + centers.back().first + centers[i].first);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:84:28: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
for(int i=0; i<N; i++) if(dist[i] == INF)
^~
dreaming.cpp:87:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
fill(dist.begin(), dist.end(), INF);
^~~~
dreaming.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<centers.size()-1; i++){
~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
50 ms |
7160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
50 ms |
7160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
50 ms |
7160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1076 ms |
5900 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
50 ms |
7160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
50 ms |
7160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |