#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include <stdio.h>
#include <stdlib.h>
const ll inf = 1e9 + 6;
#include "dreaming.h"
const int mxn = 1e5 + 5;
vt<pii>adj[mxn + 1];
int n;
bool vis[mxn + 1];
vt<int>comp;
vt<int>bfs(int s){
// bfs works since it is a tree
vt<int>dis(n + 1, -1);
queue<int>q; q.push(s); dis[s] = 0;
while(!q.empty()){
int nw = q.front(); q.pop();
for(auto [v, w]: adj[nw]){
if(dis[v] == -1){
dis[v] = dis[nw] + w;
q.push(v);
}
}
}
return(dis);
}
void dfs(int s){
vis[s] = 1; comp.pb(s);
for(auto [v, w]: adj[s]){
if(!vis[v]){
dfs(v);
}
}
}
int travelTime(int N, int m, int L, int A[], int B[], int T[]) {
n = N;
forr(i, 0, m){
int u = A[i], v = B[i], w = T[i];
adj[u].pb({v, w}); adj[v].pb({u, w});
}
int ans = 0, diam = 0;
vt<int>cand;
forr(i, 1, n + 1){
if(!vis[i]){
comp.clear();
vt<int>d1 = bfs(i);
int id = max_element(d1.begin(), d1.end()) - d1.begin();
vt<int>d2 = bfs(id);
int id2 = max_element(d2.begin(), d2.end()) - d2.begin();
vt<int>d3 = bfs(id2);
diam = max(diam, *max_element(d3.begin(), d3.end()));
dfs(i);
ll mn = inf, idd = -1;
for(auto j: comp){
ll val = max(d2[j], d3[j]);
if(val < mn){
mn = val; idd = j;
}
}
cand.pb(mn);
}
}
sort(cand.begin(), cand.end());
if(sz(cand) > 1)ans = cand[0] + cand[1] + L;
if(sz(cand) > 2)ans = max(ans, cand[1] + cand[2] + 2 * L);
return(max(ans, diam));
}
/*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
FILE *f = fopen("dreaming.in", "r");
if (!f)
fail("Failed to open input file.");
res = scanf("%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = scanf("%d%d%d", &A[i], &B[i], &T[i]);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
*/
Compilation message
dreaming.cpp: In function 'std::vector<long long int> bfs(long long int)':
dreaming.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for(auto [v, w]: adj[nw]){
| ^
dreaming.cpp: In function 'void dfs(long long int)':
dreaming.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for(auto [v, w]: adj[s]){
| ^
dreaming.cpp: In function 'long long int travelTime(long long int, long long int, long long int, long long int*, long long int*, long long int*)':
dreaming.cpp:69:26: warning: variable 'idd' set but not used [-Wunused-but-set-variable]
69 | ll mn = inf, idd = -1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
7372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
7372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
5844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
7372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
