Submission #860885

#	Time	Username	Problem	Language	Result	Execution time	Memory
860885		tosivanmak	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

#include<bits/stdc++.h>
using namespace std;
#define ll int

vector<pair<ll,ll> >adj[100005];
bool visited[100005],visited2[100005],visited3[100005];
ll dist[100005],maxdep[100005];
set<pair<ll,ll> >st[100005],st2[100005];
void dfs(ll s){
    visited[s]=true;
    maxdep[s]=dist[s];
    for(auto u: adj[s]){
        if(!visited[u.first]){
            dist[u.first]=dist[s]+u.second;
            dfs(u.first);
            maxdep[s]=max(maxdep[s],maxdep[u.first]);
        }
    }
    
}
ll find(ll s, ll longest){
     visited2[s]=true;
     ll haha=max(maxdep[s]-dist[s],longest);
     for(auto u: adj[s]){
         if(!visited2[u.first]){
             st[s].insert({maxdep[u.first],u.first});
         }
     }
     for(auto u: adj[s]){
         if(!visited2[u.first]){
             st[s].erase({maxdep[u.first],u.first});
             ll lol=u.second+longest;
             if(st[s].size()){
                pair<ll,ll> bruh=*st[s].rbegin();
                ll ok=bruh.first;
                 ok+=u.second;
                 ok-=dist[s];
                lol=max(lol,ok);
             }
             haha=min(haha,find(u.first,lol));
             st[s].insert({maxdep[u.first],u.first});
         }
     }
     return haha;
}
ll find2(ll s, ll longest){
    // cout<<s<<": "<<longest<<"\n";
     visited3[s]=true;

     ll haha=max(maxdep[s]-dist[s],longest);
     for(auto u: adj[s]){
         if(!visited3[u.first]){
             st2[s].insert({maxdep[u.first],u.first});
         }
     }
     for(auto u: adj[s]){
         if(!visited3[u.first]){
             st2[s].erase({maxdep[u.first],u.first});
             ll lol=u.second+longest;
             if(st2[s].size()){
                pair<ll,ll> bruh=*st2[s].rbegin();
                ll ok=bruh.first;
                 ok+=u.second;
                 ok-=dist[s];
                lol=max(lol,ok);
             }
             haha=max(haha,find2(u.first,lol));
             st2[s].insert({maxdep[u.first],u.first});
         }
     }
     return haha;
}
// int main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL); cout.tie(NULL);
//     ll n,m,l;
//     cin>>n>>m>>l;
//     // largest + second +l
//     // or second + third + 2*l
//     // maximum
//     for(int i=1;i<=m;i++){
//         ll u,v,t;
//         cin>>u>>v>>t;
//         adj[u].push_back({v,t});
//         adj[v].push_back({u,t});
//     }
//     vector<ll>ans,ans2;
//     for(int i=0;i<n;i++){
//         if(!visited[i]){
//             dist[i]=0;
//             dfs(i);
//             // cout<<i<<": ";
//            ans.push_back(find(i,0));
//            ans2.push_back(find2(i,0));
//         }
//     }
//     // for(int i=0;i<n;i++){
//     //     cout<<dist[i]<<" ";
//     // }
//     sort(ans.rbegin(),ans.rend());
//     sort(ans2.rbegin(),ans2.rend());
//     if(m==n-1){
//         cout<<ans2[0]<<"\n";
//     }
//     else if(m==n-2){
//         cout<<max(ans2[0],ans[0]+ans[1]+l);
//     }
//     else{
//         ll lol=ans[0]+ans[1]+l;
//         lol=max(lol,ans[1]+ans[2]+2*l);
//         lol=max(lol,ans2[0]);
//         cout<<lol<<'\n';
//     }
//     // for(auto u: ans2){
//     //     cout<<u<<"\n";
//     // }
//     // for(auto u: ans){
//     //     cout<<u<<" ";
//     // }
// }

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    int n,m,l;
   n=N,m=M,l=L;
    // largest + second +l
    // or second + third + 2*l
    // maximum
    for(int i=0;i<m;i++){
        ll u,v,t;
         u=A[i],v=B[i],t=T[i];
        adj[u].push_back({v,t});
        adj[v].push_back({u,t});
    }
    vector<int>ans,ans2;
    for(int i=0;i<n;i++){
        if(!visited[i]){
            dist[i]=0;
            dfs(i);
            // cout<<i<<": ";
           ans.push_back(find(i,0));
           ans2.push_back(find2(i,0));
        }
    }
    // for(int i=0;i<n;i++){
    //     cout<<dist[i]<<" ";
    // }
    sort(ans.rbegin(),ans.rend());
    sort(ans2.rbegin(),ans2.rend());
    if(m==n-1){
        // cout<<ans2[0]<<"\n";
        return ans2[0];
    }
    else if(m==n-2){
        return max(ans2[0],ans[0]+ans[1]+l);
    }
    else{
        ll lol=ans[0]+ans[1]+l;
        lol=max(lol,ans[1]+ans[2]+2*l);
        lol=max(lol,ans2[0]);
        return lol;
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccYFGvii.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status