#include "dreaming.h"
#include <bits/stdc++.h>
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
//don't forget to change the array sizes
vector<vector<pair<int, int> > > to;
int n;
int m;
int l;
bool vis[100010];
int dia, h;
int h1[100010], h2[100010];
void mark(int u){
vis[u] = 1;
for (pii vw : to[u]){
int v = vw.xx;
if (!vis[v]){
mark(v);
}
}
}
void dosz(int u, int pre){
int mx1 = 0, mx2 = 0;
for (pii vw : to[u]){
int v = vw.xx;
if (v != pre){
dosz(v, u);
if (mx1 < h1[v] + vw.yy){
mx2 = mx1;
mx1 = h1[v] + vw.yy;
}
else if (mx2 < h1[v] + vw.yy) mx2 = h1[v] + vw.yy;
}
}
h1[u] = mx1;
h2[u] = mx2;
}
void crawl(int u, int pre){
h = min(h, max(h1[u], h2[u]));
dia = max(dia, h1[u]);
for (pii vw : to[u]){
int v = vw.xx;
if (v != pre){
int tmpu1 = h1[u], tmpv1 = h1[v];
int tmpu2 = h2[u], tmpv2 = h2[v];
if (h1[u] == vw.yy + h1[v]){ //take the second
h1[u] = h2[u];
}
if (h1[u] + vw.yy > h1[v]){
h2[v] = h1[v];
h1[v] = h1[u] + vw.yy;
}
else if (h1[u] + vw.yy > h2[v]) h2[v] = h1[u] + vw.yy;
crawl(v, u);
h1[v] = tmpv1, h2[v] = tmpv2;
h1[u] = tmpu1, h2[u] = tmpu2;
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for (int i = 0; i < m; i++){
to[A[i]].pb(mp(B[i], T[i]) );
to[B[i]].pb(mp(A[i], T[i]) );
}
vector<int> hs;
int ans = 0;
for (int i = 0; i < n; i++){
if (!vis[i]){
h = 1e9;
dia = 0;
dosz(i, i);
crawl(i, i);
ans = max(dia, ans); //ans could be diametr of one subtree
hs.pb(h);
mark(i);
}
}
sort(hs.rbegin(), hs.rend());
if (hs.size() > 1){ // 2 or more trees
ans = max(ans, hs[0] + hs[1] + l);
}
if (hs.size() > 2){ // three or more trees
ans = max(ans, hs[1] + hs[2] + 2*l);
}
// cout << ans;
return ans;
}
// int dfs2(int )
// int main(){
// freopen("in.txt", "r", stdin);
// cin >> n >> m >> l;
// to.resize(n);
// for (int i = 0, a, b, t; i < m; i++){
// cin >> a >> b >> t;
// to[a].pb(mp(b, t));
// to[b].pb(mp(a, t));
// }
// }
//don't forget to change the array sizes
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
3832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
3832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
3832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
1656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
3832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
3832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
