#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)(1e5)+5;
vector<pair<int, int>> adj[MAXN];
int cur = -1;
int curI = -1;
pair<int, int> best;
bool visited[MAXN];
pair<int, int> sep = {(int)(1e9), (int)(1e9)};
int mx = 0;
void furthest(int n, int p, int d) {
visited[n] = true;
if (d > cur) {
cur = d;
curI = n;
}
for (pair<int, int> e : adj[n]) {
if (e.first != p) {
furthest(e.first, n, d+e.second);
}
}
}
int getBest(int n, int p, int d) {
int distTo = (n == curI ? 0 : (int)(1e9)) ;
for (pair<int, int> e : adj[n]) {
if (e.first != p) {
distTo = min(distTo, getBest(e.first, n, d+e.second) + e.second);
}
}
if (max(d, distTo) < best.first) {
best = {max(d, distTo), min(d, distTo)};
}
return distTo;
}
void getSplit(int n) {
cur = -1;
furthest(n, n, 0);
cur = -1;
int d1 = curI;
furthest(d1, d1, 0);
best = {(int)(1e9), (int)(1e9)};
getBest(d1, d1, 0);
if (n == 0) {
sep=best;
}
else if (best.first < (int)(1e9)){
if (best.first > sep.first) {
sep.second = sep.first;
sep.first = best.first;
}
else if (best.first > sep.second) {
sep.second = best.first;
}
mx = max(mx, best.first + best.second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
if (N == 1) {
return 0;
}
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]});
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
getSplit(i);
}
}
return max(sep.first + sep.second + L, mx);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
51 ms |
13804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
51 ms |
13804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
51 ms |
13804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
5100 KB |
Output is correct |
2 |
Incorrect |
21 ms |
5120 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
51 ms |
13804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
51 ms |
13804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |