| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 98708 | tduong0806 | Dreaming (IOI13_dreaming) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<ll,ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
#define read2(a,b) read(a),read(b)
#define read3(a,b,c) read(a),read(b),read(c)
const int N=100010;
ll n,m,l,a[N],dd[N],tr[N],in[N],out[N];
vector<pii> ke[N];
vector<ll> sv;
priority_queue<ll> heap;
void In(int u)
{
//cout<<u;
sv.pb(u);
dd[u]=1;
forv(v,ke[u]) if(v.fi!=tr[u])
{
tr[v.fi]=u;
In(v.fi);
in[u]=max(in[u],in[v.fi]+v.se);
}
}
void Out(int u)
{
vector<pii> e;
forv(v,ke[u]) if(v.fi!=tr[u])
{
out[v.fi]=max(out[v.fi],out[u]+v.se);
e.pb({in[v.fi]+v.se,v.fi});
}
sort(all(e),greater<pii>());
if(e.size()>1) forv(v,ke[u]) if(v.fi!=tr[u])
{
if(v.fi==e[0].se) out[v.fi]=max(out[v.fi],e[1].fi+v.se);
else out[v.fi]=max(out[v.fi],e[0].fi+v.se);
}
forv(v,ke[u]) if(v.fi!=tr[u]) Out(v.fi);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("DREAMING.inp","r",stdin);
//freopen("DREAMING.out","w",stdout);
cin>>n>>m>>l;
forinc(i,1,m)
{
ll u,v,c;
cin>>u>>v>>c;
++u,++v;
//cout<<u<<" "<<v<<" "<<c<<endl;
ke[u].pb({v,c});
ke[v].pb({u,c});
}
forinc(i,1,n) if(!dd[i])
{
In(i);Out(i);
ll ma=1e17;
forv(x,sv)
{
//cout<<x<<" "<<in[x]<<" "<<out[x]<<endl;
ma=min(ma,max(in[x],out[x]));
}
cout<<endl;
sv.clear();
heap.push(ma);
}
ll kq=0;
forinc(i,1,n)
{
//cout<<in[i]<<" "<<out[i]<<endl;
kq=max(kq,in[i]+out[i]);
}
while(heap.size()>1)
{
ll u=heap.top();heap.pop();
ll v=heap.top();heap.pop();
kq=max(kq,u+v+l);
heap.push(max(u,v)+l);
}
cout<<kq;
}