#include <bits/stdc++.h>
#include "dreaming.h"
#define edge pair<int, int>
#define to first
#define cost second
using namespace std;
const int MAX_N = 123456;
vector<edge> adj[MAX_N]; vector<int> R;
bool visited[MAX_N];
int maxdist, point;
edge parent[MAX_N];
void dfs1(int u, int par, int val) {
int i, mx = 0;
if(val > maxdist) {
maxdist = val;
point = u;
}
for(i = 0; i < (int) adj[u].size(); i++) {
edge v = adj[u][i];
if(v.to == par) continue;
dfs1(v.to, u, v.cost + val);
}
}
void dfs2(int u, int par, int val) {
visited[u] = 1;
int i, mx = 0;
if(val > maxdist) {
maxdist = val;
point = u;
}
for(i = 0; i < (int) adj[u].size(); i++) {
edge v = adj[u][i];
if(v.to == par) continue;
parent[v.to] = edge(u, v.cost);
dfs2(v.to, u, val+v.cost);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int i, ans = 0;
for(i = 0; i < M; i++) {
adj[A[i]].push_back(edge(B[i], T[i]));
adj[B[i]].push_back(edge(A[i], T[i]));
}
for(i = 0; i < N; i++) {
if(visited[i]) continue;
maxdist = -1; dfs1(i, i, 0); int one = point;
maxdist = -1; dfs2(one, one, 0); int two = point;
ans = max(ans, maxdist);
int able = maxdist/2, d = 0;
for(i = two; i != one; i = parent[i].to) {
if(d + parent[i].cost > able) {
d = min(d + parent[i].cost, maxdist-d);
break;
} d += parent[i].cost;
} R.push_back(d);
} sort(R.begin(), R.end(), greater<int>());
if(R.size() > 1) ans = max(ans, R[0]+L+R[1]);
if(R.size() > 2) ans = max(ans, R[1]+L+L+R[2]);
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs1(int, int, int)':
dreaming.cpp:16:12: warning: unused variable 'mx' [-Wunused-variable]
int i, mx = 0;
^~
dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:33:12: warning: unused variable 'mx' [-Wunused-variable]
int i, mx = 0;
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
12280 KB |
Output is correct |
2 |
Correct |
62 ms |
12144 KB |
Output is correct |
3 |
Correct |
61 ms |
9208 KB |
Output is correct |
4 |
Correct |
11 ms |
4608 KB |
Output is correct |
5 |
Correct |
10 ms |
4096 KB |
Output is correct |
6 |
Correct |
17 ms |
5248 KB |
Output is correct |
7 |
Incorrect |
7 ms |
3328 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
12280 KB |
Output is correct |
2 |
Correct |
62 ms |
12144 KB |
Output is correct |
3 |
Correct |
61 ms |
9208 KB |
Output is correct |
4 |
Correct |
11 ms |
4608 KB |
Output is correct |
5 |
Correct |
10 ms |
4096 KB |
Output is correct |
6 |
Correct |
17 ms |
5248 KB |
Output is correct |
7 |
Incorrect |
7 ms |
3328 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
12280 KB |
Output is correct |
2 |
Correct |
62 ms |
12144 KB |
Output is correct |
3 |
Correct |
61 ms |
9208 KB |
Output is correct |
4 |
Correct |
11 ms |
4608 KB |
Output is correct |
5 |
Correct |
10 ms |
4096 KB |
Output is correct |
6 |
Correct |
17 ms |
5248 KB |
Output is correct |
7 |
Incorrect |
7 ms |
3328 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
6784 KB |
Output is correct |
2 |
Correct |
30 ms |
6780 KB |
Output is correct |
3 |
Correct |
27 ms |
6776 KB |
Output is correct |
4 |
Correct |
33 ms |
6780 KB |
Output is correct |
5 |
Correct |
29 ms |
6776 KB |
Output is correct |
6 |
Correct |
32 ms |
7292 KB |
Output is correct |
7 |
Correct |
35 ms |
6876 KB |
Output is correct |
8 |
Correct |
27 ms |
6784 KB |
Output is correct |
9 |
Correct |
27 ms |
6692 KB |
Output is correct |
10 |
Correct |
29 ms |
6908 KB |
Output is correct |
11 |
Correct |
4 ms |
3200 KB |
Output is correct |
12 |
Correct |
8 ms |
4476 KB |
Output is correct |
13 |
Correct |
8 ms |
4476 KB |
Output is correct |
14 |
Correct |
8 ms |
4476 KB |
Output is correct |
15 |
Correct |
9 ms |
4476 KB |
Output is correct |
16 |
Correct |
8 ms |
4348 KB |
Output is correct |
17 |
Correct |
8 ms |
4092 KB |
Output is correct |
18 |
Correct |
8 ms |
4600 KB |
Output is correct |
19 |
Correct |
8 ms |
4348 KB |
Output is correct |
20 |
Correct |
4 ms |
3200 KB |
Output is correct |
21 |
Correct |
4 ms |
3200 KB |
Output is correct |
22 |
Correct |
5 ms |
3328 KB |
Output is correct |
23 |
Correct |
8 ms |
4476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
12280 KB |
Output is correct |
2 |
Correct |
62 ms |
12144 KB |
Output is correct |
3 |
Correct |
61 ms |
9208 KB |
Output is correct |
4 |
Correct |
11 ms |
4608 KB |
Output is correct |
5 |
Correct |
10 ms |
4096 KB |
Output is correct |
6 |
Correct |
17 ms |
5248 KB |
Output is correct |
7 |
Incorrect |
7 ms |
3328 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
12280 KB |
Output is correct |
2 |
Correct |
62 ms |
12144 KB |
Output is correct |
3 |
Correct |
61 ms |
9208 KB |
Output is correct |
4 |
Correct |
11 ms |
4608 KB |
Output is correct |
5 |
Correct |
10 ms |
4096 KB |
Output is correct |
6 |
Correct |
17 ms |
5248 KB |
Output is correct |
7 |
Incorrect |
7 ms |
3328 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |