| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 38121 | minchurl | 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>
#define MAX_N 100005
#define pb push_back
#define inf 0x7fffffff
using namespace std;
struct node{
int y,cost;
};
struct cmp{
bool operator()(node x,node y){
if(x.cost==y.cost) return x.y<y.y;
return x.cost>y.cost;
}
};
int N,M,L,an,b[MAX_N],bn,ans;
bool c1[MAX_N],c2[MAX_N],c3[MAX_N];
node arr[MAX_N],X,Y;
vector<node> net[MAX_N];
set<node,cmp> S;
void is_far(int x,int cost){
int sz;
node y;
c1[x]=true;
sz=net[x].size();
if(X.cost<cost){
X.cost=cost;
X.y=x;
}
while(sz--){
y=net[x][sz];
if(c1[y.y]) continue;
is_far(y.y,cost+y.cost);
}
}
void find_Diameter(int x,int cost){
int sz;
node y;
c2[x]=true;
sz=net[x].size();
if(Y.cost<cost){
Y.cost=cost;
Y.y=x;
}
while(sz--){
y=net[x][sz];
if(c2[y.y]) continue;
find_Diameter(y.y,cost+y.cost);
}
}
int make_arr(int x){
int sz,maxx=0,k;
bool z;
node y;
c3[x]=true;
sz=net[x].size();
if(sz==1 && x==Y.y){
arr[an].y=0;
arr[an++].cost=0;
return -1;
}
while(sz--){
y=net[x][sz];
if(c3[y.y]) continue;
y.y=make_arr(y.y);
if(y.y==-1){
z=true;
k=y.cost;
continue;
}
y.y+=y.cost;
maxx=max(maxx,y.y);
}
if(!z) return maxx;
arr[an].y=maxx;
arr[an++].cost=k;
return -1;
}
int main(){
int i,j,x,y,z,cost;
node p;
scanf("%d %d %d",&N,&M,&L);
for(i=0;i<M;i++){
scanf("%d %d %d",&x,&y,&cost);
p.y=y;p.cost=cost;
net[x].pb(p);
p.y=x;
net[y].pb(p);
}
for(i=0;i<N;i++){
if(c1[i]) continue;
X.y=X.cost=0;
is_far(i,0);
ans=max(ans,X.cost);
Y.y=Y.cost=0;
find_Diameter(X.y,0);
ans=max(ans,Y.cost);
an=0;
S.clear();
x=make_arr(X.y);
x=0;
z=inf;
for(j=1;j<an;j++){
x+=arr[j].cost;
p.y=j;
p.cost=x+arr[j].y;
S.insert(p);
}
x=0;
y=0;
for(j=0;j<an;j++){
x+=arr[j].cost;
y+=arr[j].cost;
while(!S.empty()){
p=(*S.begin());
if(p.y<=j) S.erase(p);
else break;
}
x=max(x,arr[j].y);
if(!S.empty()){
p=(*S.begin());
z=min(max(x,p.cost-y),z);
}else z=min(z,x);
}
b[bn++]=z;
}
sort(b,b+bn);
if(bn>=2){
x=b[bn-1];
y=b[bn-2];
ans=max(ans,x+y+L);
}
if(bn>2){
x=b[bn-2];
y=b[bn-3];
ans=max(ans,x+y+2*L);
}
printf("%d\n",ans);
return 0;
}