// My Header
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
#define mp make_pair
#define f first
#define s second
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
#include "dreaming.h"
vb vis1,vis2;
vi dist1,par,pdist;
vector<vii> adj;
int furthest=0; int far=0;
void far1(int nd){
vis1[nd] = 1;
for(auto&[cost, nei]:adj[nd]) if (!vis1[nei]) {
dist1[nei] = dist1[nd] + cost;
far1(nei);
}
if (dist1[nd] > furthest){
furthest = dist1[nd];
far = nd;
}
}
void far2(int nd){
vis2[nd] = 1;
for(auto&[cost, nei]:adj[nd]) if (!vis2[nei]) {
par[nei] = nd;
pdist[nei] = cost;
dist1[nei] = dist1[nd] + cost;
far2(nei);
}
if (dist1[nd] > furthest){
furthest = dist1[nd];
far = nd;
//cout << "foo " << far << endl;
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
adj.rsz(n);
vis1.rsz(n);
vis2.rsz(n);
dist1.rsz(n);
par.rsz(n);
pdist.rsz(n);
fill(all(vis1),0);
fill(all(vis2),0);
fill(all(dist1),0);
fill(all(par),0);
fill(all(pdist),0);
F0R(i, m){
adj[a[i]].pb({t[i],b[i]});
adj[b[i]].pb({t[i],a[i]});
}
int greatestTravelTime = 0;
vi radii;
F0R(i, n){
if (vis1[i]) continue;
furthest = 0;
far = i;
dist1[i] = 0;
far1(i);
int xx = far;
furthest = 0;
far = xx;
dist1[xx] = 0;
far2(xx);
int yy = far;
if (xx==yy){
radii.pb(0);
continue;
}
//cout << i << " " << xx << " " << yy << endl;
int dd = furthest;
greatestTravelTime = max(greatestTravelTime,dd);
cout << dd << endl;
vi dists;
int cur = yy;
while(cur != xx){
dists.pb(pdist[cur]);
cur = par[cur];
}
//trav(k, dists) cout << k << " "; cout << endl;
int radius;
int dsum = 0;
if (dsum >= dd/2) radius = dsum;
else trav(d, dists){
dsum += d;
if (dsum >= dd/2){ radius = dsum; break;}
}
reverse(all(dists));
dsum = 0;
if (dsum >= dd/2) radius = min(radius,dsum);
else trav(d, dists){
dsum += d;
if (dsum >= dd/2){ radius = min(radius,dsum); break;}
}
radii.pb(radius);
}
trav(i, radii) cout << i << " "; cout << endl;
int rs = radii.size();
sort(all(radii),greater<int>());
if (rs>1){
greatestTravelTime = max(greatestTravelTime,radii[0]+radii[1]+l);
}
if (rs>2){
greatestTravelTime = max(greatestTravelTime,radii[2]+radii[1]+2*l);
}
return greatestTravelTime;
}
/*
#include <stdio.h>
#include <stdlib.h>
#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 = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}*/
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:40:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
40 | #define trav(a,x) for (auto& a: x)
| ^~~
dreaming.cpp:179:5: note: in expansion of macro 'trav'
179 | trav(i, radii) cout << i << " "; cout << endl;
| ^~~~
dreaming.cpp:179:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
179 | trav(i, radii) cout << i << " "; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
12796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
12796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
6888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
12796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
