#include "dreaming.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=1e5+5;
int n,m,cnt,l[N],r[N],Time,root,dep[N],last,ST[4*N],lazy[4*N];
pii val[N];
vector<int>adj[N],a,b,w;
vector<pii>g[N];
bool vis[N];
vector<int>go;
void dolazy(int id,int l,int r)
{
if (lazy[id]==0) return;
ST[id]+=lazy[id];
if (l!=r)
{
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
}
lazy[id]=0;
}
void update(int id,int l,int r,int L,int R,int val)
{
dolazy(id,l,r);
if (r<L||R<l) return;
if(L<=l&&r<=R)
{
ST[id]+=val;
if (l!=r)
{
lazy[id*2]+=val;
lazy[id*2+1]+=val;
}
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,L,R,val);
update(id*2+1,mid+1,r,L,R,val);
ST[id]=max(ST[id*2],ST[id*2+1]);
}
int get (int id,int l,int r,int L,int R)
{
dolazy(id,l,r);
if (r<L||R<l) return -1e9;
if (L<=l&&r<=R) return ST[id];
int mid=(l+r)/2;
return max (get (id*2,l,mid,L,R),get (id*2+1,mid+1,r,L,R));
}
void dfs(int u)
{
go.push_back(u);
vis[u]=true;
Time++;
l[u]=Time;
for(auto&id:adj[u])
{
int v=a[id]+b[id]-u;
if(vis[v]) continue;
dep[v]=dep[u]+w[id];
dfs(v);
}
r[u]=Time;
}
void calc(int u)
{
vis[u]=true;
val[cnt]=min(val[cnt],mp(get(1,1,n,l[root],r[root]),u));
//if(root==0) cout<<u<<' '<<l[root]<<' '<<r[root]<<' '<<get(1,1,n,l[root],r[root])<<' '<<val[cnt].fi<<'\n';
for(auto&id:adj[u])
{
int v=a[id]+b[id]-u;
if(vis[v]) continue;
update(1,1,n,l[root],r[root],w[id]);
update(1,1,n,l[v],r[v],-2*w[id]);
calc(v);
update(1,1,n,l[root],r[root],-w[id]);
update(1,1,n,l[v],r[v],2*w[id]);
}
}
void fin(int u,int p)
{
if(dep[u]>dep[last]) last=u;
for(auto&v:g[u])
{
if(v.fi==p) continue;
dep[v.fi]=dep[u]+v.se;
fin(v.fi,u);
}
}
int travelTime(int num,int m,int t,int a[],int b[],int w[])
{
n=num;
for(int i=0;i<m;i++)
{
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
cnt=0;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
root=i;
go.clear();
dfs(i);
for(auto&u:go)
{
//if(!i) cout<<l[u]<<' '<<dep[u]<<'\n';
vis[u]=false;
update(1,1,n,l[u],l[u],dep[u]);
}
//cout<<'\n';
cnt++;
val[cnt]=mp(1e9,0);
calc(i);
//cout<<val[cnt].fi<<'\n';
}
}
sort(val+1,val+cnt+1);
int p=val[cnt].se;
for(int i=cnt-1;i>=1;i--)
{
g[p].push_back(mp(val[i].se,t));
g[val[i].se].push_back(mp(p,t));
//cout<<val[i].se<<' '<<p<<' '<<t<<'\n';
}
for(int i=0;i<m;i++)
{
g[a[i]].push_back(mp(b[i],w[i]));
g[b[i]].push_back(mp(a[i],w[i]));
//cout<<a[i]<<' '<<b[i]<<' '<<w[i]<<'\n';
}
fin(0,-1);
dep[last]=0;
fin(last,-1);
return dep[last];
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int l;
cin>>n>>m>>l;
a.resize(m),b.resize(m),w.resize(m);
for(int i=0;i<m;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
for(int i=0;i<m;i++) cin>>w[i];
cout<<travelTime(n,m,l,a,b,w);
}
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
18040 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 |
58 ms |
18040 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 |
58 ms |
18040 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 |
29 ms |
14720 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 |
58 ms |
18040 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 |
58 ms |
18040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
