#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int maxN = (int) 1e5 + 1;
vector<pair<int,int>> adj[maxN];
int cnt = 0, n, m, l,sz = 0, ans = 0;
bool vis[maxN];
int parent[maxN];
pair<int, int> p[maxN];
void init() {
memset(parent, -1, sizeof(parent));
}
pair<int, int> bfs(int node) {
sz = 0;
bool seen[n];
int depth[n];
memset(seen, 0, sizeof(seen));
memset(depth, 0, sizeof(depth));
int best_node = node, best_dist = 0;
depth[node] = 0;
seen[node] = true; vis[node] = true;
queue<int> qs;
qs.emplace(node);
while(!qs.empty()) {
auto f = qs.front();
sz++;
if (depth[f] > best_dist) {
best_dist = depth[f];
best_node = f;
}
qs.pop();
for (auto x : adj[f]) {
if (seen[x.first]) continue;
vis[x.first] = true;
qs.emplace(x.first);
parent[x.first] = f;
depth[x.first] = x.second + depth[f];
seen[x.first] = true;
}
}
return make_pair(best_node, best_dist);
}
int Get_total(int node) {
auto val = bfs(node);
auto f = bfs(val.first);
return f.second;
}
void Do(int node) {
auto val = bfs(node);
if (sz == 1) {
p[cnt++] = make_pair(0, node);
return ;
}
auto Tke = bfs(val.first);
parent[val.first] = -1;
int cur = Tke.first;
vector<int> path, len;
while(cur != -1) {
int nxt = parent[cur];
path.emplace_back(cur);
if (nxt == -1) break;
auto q = lower_bound(adj[cur].begin(), adj[cur].end(), make_pair(nxt, 0));
len.emplace_back((*q).second);
cur = parent[cur];
}
int Max = (int)1e9, best_node = -1, s = 0;
for (int i = 0; i < (int)path.size(); i++) {
if (i > 0) s += len[i - 1];
int now_max = max(s, Tke.second - s);
if (now_max < Max) {
Max = now_max;
best_node = path[i];
}
}
ans = max(ans, Tke.second);
assert(best_node != -1);
p[cnt++] = make_pair(Max, best_node);
return ;
}
void make() {
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
Do(i);
vis[i] = true;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
m = M;
l = L;
init();
for (int i = 0; i < m; i++) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(),adj[i].end());
}
make();
sort(p.rbegin(), p.rend());
if (cnt >= 2) {
ans = max(ans, p[0].first + p[1].first + l);
}
if (cnt >= 3) {
ans = max(ans, p[1].first + p[2].first + 2 * l);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:114:10: error: request for member 'rbegin' in 'p', which is of non-class type 'std::pair<int, int> [100001]'
114 | sort(p.rbegin(), p.rend());
| ^~~~~~
dreaming.cpp:114:22: error: request for member 'rend' in 'p', which is of non-class type 'std::pair<int, int> [100001]'
114 | sort(p.rbegin(), p.rend());
| ^~~~
