#include <bits/stdc++.h>
#define pb push_back
#define task "sequence"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
using ll = int;
const long long mod = 1e9+7;
const ll N = 2e5 + 5;
const int base = 350;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, a[N], cnt, d[N], l, r, ans, u, tong, v, in[N], out[N], st[N*4], lazy[N*4];
ll x[N], y[N], w[N];
vector<ll> kq, adj[N];
void down(ll id)
{
if(lazy[id] == 0)return;
st[id*2] += lazy[id];
st[id*2+1] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id*2] += lazy[id];
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll val)
{
if(u <= l && r <= v)
{
st[id] += val;
lazy[id] += val;
return;
}
if(u > r || l > v)return;
down(id);
ll mid = (l + r) / 2;
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
st[id] = max(st[id*2], st[id*2+1]);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v)return 0;
ll mid = (l + r) / 2;
down(id);
return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
void dfs1(ll u)
{
cout << u <<" ";
in[u] = ++r;
if(d[u] > d[k])k = u;
a[u] = 1;
update(1, 1, n, r, r, d[u]);
for(ll j : adj[u])
{
ll v = x[j] + y[j] - u;
if(a[v] == 1)continue;
d[v] = d[u] + w[j];
dfs1(v);
}
out[u] = r;
}
void dfs(ll u, ll l, ll r)
{
a[u] = 0;
for(ll j : adj[u])
{
ll v = x[j] + y[j] - u;
if(a[v] == 0)continue;
update(1, 1, n, l, r, w[j]);
update(1, 1, n, in[v], out[v], -2*w[j]);
tong = min(tong, get(1, 1, n, l, r));
dfs(v, l, r);
update(1, 1, n, l, r, -w[j]);
update(1, 1, n, in[v], out[v], +2*w[j]);
}
}
void dfs2(ll u)
{
if(d[u] > ans)ans = d[u];
a[u] = 2;
for(ll j : adj[u])
{
ll v = x[j] + y[j] - u;
if(a[v] == 2)continue;
d[v] = d[u] + w[j];
dfs2(v);
}
}
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 ++)x[i] = A[i];
for(int i = 0; i < m; i ++)y[i] = B[i];
for(int i = 0; i < m; i ++)
{
w[i] = T[i];
adj[x[i]].pb(i);
adj[y[i]].pb(i);
}
d[n] = -1;
for(int i = 0; i < n; i ++)
{
if(a[i] == 0)
{
k = n;
dfs1(i);
tong = get(1, 1, n, in[i], out[i]);
//cout << tong <<" ";
dfs(i, in[i], out[i]);
kq.pb(tong);
d[k] = 0;
dfs2(k);
//cout << tong << '\n';
}
}
sort(kq.rbegin(), kq.rend());
if(kq.size() > 1)ans = max(ans, kq[0] + kq[1] + l);
if(kq.size() > 2)ans = max(ans, kq[2] + kq[1] + l*2);
return ans;
}
/*
int main()
{
if(fopen(task".in", "r")){
freopen(task".in", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ntest;
ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
12 8 2
0 8 2 5 5 1 1 10
8 2 7 11 1 3 9 6
4 2 4 3 7 1 5 3
*/
Compilation message
/tmp/cc5MhhlT.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
