Submission #922270

#	Time	Username	Problem	Language	Result	Execution time	Memory
922270		Aiperiii	꿈 (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int NN=1e5+5;
int l[NN],d[NN],p[NN];
vector <int> gr[NN];
vector <pair <int,int> >g[NN];
int find_set(int v){
   if(l[v]==v)return v;
   return l[v]=find_set(l[v]);
}
void union_set(int u,int v){
   u=find_set(u);
   v=find_set(v);
   if(u!=v){
     if(gr[v].size()<gr[u].size())swap(u,v);
     l[u]=v;
     for(auto x : gr[u])gr[v].pb(x);
     gr[u].clear();
   }
}
void bfs(int v){
   queue <int> q;
   q.push(v);
   while(!q.empty()){
      int v=q.front();
      q.pop();
      for(auto to : g[v]){
         if(d[to.ff]==-1){
            p[to.ff]=v;
            d[to.ff]=d[v]+to.ss;
            q.push(to.ff);
         }
      }
   }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
   for(int i=0;i<N;i++){
      l[i]=i;
      gr[i].pb(i);
   }
   for(int i=0;i<M;i++){
      union_set(A[i],B[i]);
      g[A[i]].pb({B[i],T[i]});
      g[B[i]].pb({A[i],T[i]});
   }
   vector <int> len;
   int ans=0;
   for(int i=0;i<N;i++)d[i]=-1;
   for(int i=0;i<N;i++){
      if(gr[i].size()!=0){
         d[gr[i][0]]=0;
         bfs(gr[i][0]);
         int mx=0,node=gr[i][0];
         for(auto x : gr[i]){
            if(d[x]>mx){
               mx=d[x];
               node=x;
            }
            d[x]=-1;
            p[x]=0;
         }
         d[node]=0;
         bfs(node);
         mx=0;
         int s=node;
         for(auto x : gr[i]){
            if(d[x]>mx){
               mx=d[x];
               node=x;
            }
         }
         ans=max(ans,mx);
         vector <int> path;
         path.pb(node);
         while(node!=s){
            node=p[node];
            path.pb(node);
         }
         int mn=1e9+5;
         for(auto x : path){
            mn=min(max(mx-d[x],d[x]),mn);
         }
         len.pb(mn);
         for(auto x : gr[i]){
            d[x]=-1;
            p[x]=0;
         }
      }
   }
   sort(all(len));
   for(auto x : len)ans=max(ans,x);
   if(len.size()>=2)ans=max(ans,L+len[len.size()-1]+len[len.size()-2]);
   if(len.size()>=3)ans=max(ans,2*L+len[len.size()-2]+len[len.size()-3]);
   return ans;
}

signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int n,m,l;
   cin>>n>>m>>l;
   int a[m],b[m],c[m];
   for(int i=0;i<m;i++){
      cin>>a[i]>>b[i]>>c[i];
   }
   
   cout<<travelTime(n,m,l,a,b,c);
}

/*
 12 8 2
 0 8 4
 8 2 2
 2 7 4
 5 11 3
 5 1 7
 1 3 1
 1 9 5
 10 6 3

 */

Compilation message (stderr)

/usr/bin/ld: /tmp/cc0WjQrB.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccu1A2aE.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status