| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 448392 | tphuc2908 | Dreaming (IOI13_dreaming) | C++14 | 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.
/**
_author_ : nguyenlethienphuc
problems_ID: heap_prob1
*/
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization("unroll-loops");
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)((x).size())
#define fill(x, y) memset(y, x, sizeof(y))
#define all(x) (x).begin(), (x).end()
#define ci(x) long long x; cin>>x;
#define cii(x, y) int x, y; cin>>x>>y;
#define ciii(x, y, z) ll x, y, z; cin>>x>>y>>z;
#define TC(x) ci(x); while(x --)
#define rep(i, x, y) for ( int i = x; i <= y; i ++)
#define repi(i, x, y) for ( int i = x; i >= y; i --)
#define fore(itr, x) for ( = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x) for (itr = x.end() - 1; itr != x.begin() - 1; itr --)
#define endl "\n"
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> graph;
typedef long long ll;
const ll inf = 1e15 + 5;
const double eps = 0;
const int ms = 0;
const int md = 0;
const int mod = 2017;
void readfile(){
freopen("textin.inp", "r", stdin);
freopen("text.out", "w", stdout);
}
ll n, m, l, Max = LLONG_MIN;
pair<ll, ll> res = {0, 0};
vi ranks, path, vis;
vector<vector<pair<ll, ll> > > g;
vi st;
vector<pair<ll, ll> >center;
void dfs(int s){
st.push_back(s);
vis[s] = 1;
for(auto v : g[s]){
if(ranks[v.first]==-1){
ranks[v.first] = ranks[s] + v.second;
path[v.first] = s;
dfs(v.first);
}
}
}
bool cmp(pair<ll,ll> a, pair<ll,ll> b){
return a.second > b.second;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> l;
g.resize(n+1);
vis.resize(n+1, 0);
rep(i,1,m){
ciii(u, v, w);
g[u+1].pb(mp(v+1, w));
g[v+1].pb(mp(u+1, w));
}
ranks.resize(n+1, -1);
path = ranks;
int cnt = 0;
rep(i,1,n){
if(vis[i]==0){
//cout << i << ": " << endl;
++cnt;
st.clear();
ranks[i] = 0;
dfs(i);
pair<ll, ll> res = {-1, -1};
rep(i,0,(int)st.size()-1){
//cout << st[i] << " " << ranks[st[i]] << endl;
if(ranks[st[i]]>res.second){
res = mp(st[i], ranks[st[i]]);
}
}
ranks.assign(n+1, -1);
path[res.first] = 0;
ranks[res.first] = 0;
st.clear();
dfs(res.first);
res = {-1, -1};
rep(i,0,(int)st.size()-1){
if(ranks[st[i]]>res.second){
res = mp(st[i], ranks[st[i]]);
}
}
Max = max(Max, res.second);
ll temp = res.first;
pair<ll,ll> ans = {-1,LONG_MAX};
while(temp!=0){
//cout << ranks[temp] << " " << ranks[res.first] - ranks[temp] << endl;
if(ans.second > max(ranks[temp], ranks[res.first] - ranks[temp])){
ans = {temp, max(ranks[temp], ranks[res.first] - ranks[temp])};
}
temp = path[temp];
}
center.pb(ans);
}
}
ll Max1= 0, Max2 = 0;
sort(all(center), cmp);
if(cnt>=2){
Max1 = l + center[0].second + center[1].second;
}
if(cnt>=3){
Max2 = 2*l + center[1].second + center[2].second;
}
cout << max({Max, Max1, Max2});
return 0;
}