| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 31797 | dongwon0427 | Dreaming (IOI13_dreaming) | C++98 | 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>
using namespace std;
int n,m,l,M;
struct _tuple {
int idx,val;
};
vector<_tuple> graph[100005];
int vt1[100005],vt2[100005],via[100005],depth[100005];
pair<int,int> dfs1(int idx) {
vt1[idx]=M;
pair<int,int> ret=pair<int,int>(0,idx);
for(int i=0;i<graph[idx].size();i++) {
if(vt1[graph[idx][i].idx]==0) {
pair<int,int> tmp;
tmp = dfs1(graph[idx][i].idx);
if(ret.first < tmp.first + graph[idx][i].val) {
ret.first=tmp.first+graph[idx][i].val;
ret.second=tmp.second;
}
}
}
return ret;
}
pair<int,int> dfs2(int idx) {
vt2[idx]=1;
pair<int,int> ret=pair<int,int>(0,idx);
for(int i=0;i<graph[idx].size();i++) {
if(vt1[graph[idx][i].idx]==M && vt2[graph[idx][i].idx]==0) {
via[graph[idx][i].idx]=idx;
pair<int,int> tmp = dfs2(graph[idx][i].idx);
if(tmp.first +graph[idx][i].val > ret.first) {
ret.first = tmp.first+graph[idx][i].val;
ret.second = tmp.second;
}
}
}
depth[idx] = ret.first;
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>l;
for(int i=0;i<m;i++) {
int t1,t2,t3;
cin>>t1>>t2>>t3;
_tuple tmp;
tmp.idx=t2;tmp.val=t3;
graph[t1].push_back(tmp);
tmp.idx=t1;
graph[t2].push_back(tmp);
}
vector<pair<int,int> > rad;
for(int i=0;i<n;i++) {
if(vt1[i]==0) {
M++;
pair<int,int> tmp = dfs1(i);
via[tmp.second]=-1;
pair<int,int> tmp2 = dfs2(tmp.second);
int idx = tmp2.second;
int dia = tmp2.first;
int dis = 0;
while(idx!=-1) {
dis = max(dis,min(depth[idx],dia-depth[idx]));
idx=via[idx];
}
rad.push_back(pair<int,int>(dia-dis,dis));
}
}
sort(rad.begin(),rad.end());
//for(int i=0;i<rad.size();i++) cout<<rad[i].first<<' '<<rad[i].second<<"\n";
//cout<<"\n";
if(rad.size()>=2) cout<<rad.back().first + max(rad.back().second, rad[rad.size()-2].first + l);
else cout<<rad.back().first + rad.back().second;
return 0;
}