#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 1e5+5;
vector<pair<int,int>> adj[MAXN];
bool visited[MAXN], visited2[MAXN];
pair<int,int> dijkstra(bool *vis, int src){
int maxn = -1, pos = -1;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,src}); vis[src] = true;
while(!pq.empty()){
int u = pq.top().second, cdist = pq.top().first; pq.pop();
for(auto p : adj[u]){ //first node, then weight
if(!vis[p.first]){
vis[p.first] = true;
pq.push({cdist+p.second,p.first});
if(cdist+p.second > maxn){
maxn = cdist+p.second;
pos = p.first;
}
}
}
}
return {maxn,pos};
}
int res,laenge;
bool calc(int u, int b, int p, int d){
if(u == b) return true;
for(auto v : adj[u]){
if(v.first != p){
if(calc(v.first,b,u,d+v.second)){
res = min(res,max(d,laenge-d));
return true;
}
}
}
return false;
}
int get_dia(int x){
int a = dijkstra(visited2,x).second;
pair<int,int> ret = dijkstra(visited,a); //first is the longest path, second the second node on the longest path
res = ret.first; laenge = ret.first;
calc(a,ret.second,-1,0); //find the smallest value on the path
//cout << x << " " << res << "\n";
return res;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
memset(visited,false,sizeof(visited));
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]});
}
int ans = 0;
for(int i = 0;i<N;++i){
if(!visited[i]){
int a = dijkstra(visited2,i).second;
pair<int,int> ret = dijkstra(visited,a); //first is the longest path, second the second node on the longest path
ans = max(ans,ret.second);
}
}
memset(visited,false,sizeof(visited)); memset(visited2,false,sizeof(visited2));
vector<int> dias;
for(int i = 0;i<N;++i){
if(!visited[i]){
dias.push_back(get_dia(i));
}
}
sort(dias.rbegin(),dias.rend());
if(dias.size() > 1){
ans = max(ans,dias[0]+dias[1]+L);
}
if(dias.size() > 2){
ans = max(ans,dias[1]+dias[2]+2*L);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
13624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
13624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
13624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
