Submission #860884

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
860884	2023-10-14T17:58:33 Z	tosivanmak	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KB

dreaming

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

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

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:158:38: error: no matching function for call to 'max(long long int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
  158 |         lol=max(lol,ans[1]+ans[2]+2*l);
      |                                      ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
dreaming.cpp:158:38: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  158 |         lol=max(lol,ans[1]+ans[2]+2*l);
      |                                      ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
dreaming.cpp:158:38: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  158 |         lol=max(lol,ans[1]+ans[2]+2*l);
      |                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
dreaming.cpp:158:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  158 |         lol=max(lol,ans[1]+ans[2]+2*l);
      |                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
dreaming.cpp:158:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  158 |         lol=max(lol,ans[1]+ans[2]+2*l);
      |                                      ^
dreaming.cpp:159:28: error: no matching function for call to 'max(long long int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
  159 |         lol=max(lol,ans2[0]);
      |                            ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
dreaming.cpp:159:28: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  159 |         lol=max(lol,ans2[0]);
      |                            ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
dreaming.cpp:159:28: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  159 |         lol=max(lol,ans2[0]);
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
dreaming.cpp:159:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  159 |         lol=max(lol,ans2[0]);
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
dreaming.cpp:159:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  159 |         lol=max(lol,ans2[0]);
      |                            ^