Submission #492117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492117	2021-12-05T14:06:43 Z	aci	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define INF 1000000
typedef pair<int, int> pi;

vector<vector<pi>> t;
vector<bool> used;
vector<bool> used2;


int n, m, l;
int d, r;
vector<pi> dist;
vector<int> el;

void dfs1(int u, int p)
{
    used[u] = 1;
    el.push_back(u);
    for (pi v : t[u])
    {
        if(v.first!=p && !used[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs1(v.first, u);
        }
    }
}

void dfs2(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].second = dist[u].second + v.second;
            dfs2(v.first, u);
        }
    }
}
void dfs3(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs3(v.first, u);
        }
    }
}

bool cmp(pi a, pi b)
{
    return (a.second > b.second);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    
    n = N;
    m = M;
    l = L;

    t.resize(n);
    used.resize(n, 0);
    dist.resize(n, {-1, -1});
    used2.resize(n, 0);

    for (int i=0; i<m; i++)
    {
        int x, y, w;
        x = A[i];
        y = B[i];
        w = T[i];

        t[x].push_back({y, w});
        t[y].push_back({x, w});
    }
    vector<pi> comp;
    

    for (int i=0; i<n; i++)
    {
        
        if(!used[i])
        {
            
            dist[i].first =0;
            el.clear();
            dfs1(i, i);
            //cout<< endl;
            used2.assign(n, 0);
            int ind=i, mx = 0;
            d = 0;
            r = INF;
            for (int j : el)
            {
                if(dist[j].first > mx)
                {
                    mx = dist[j].first;
                    ind = j;
                }
            }

            dist[ind].second = 0;
            dfs2(ind, ind);
            
    
            for (int j : el)
            {
                if(dist[j].second > d)
                {
                    d = dist[j].second;
                    ind = j;
                }
            }
            used2.assign(n, 0);
            dist[ind].first = 0;
            dfs3(ind, ind);
            //for (int j : el) //cout<<j<<" "<< dist[j].first<<" "<<dist[j].second<<endl;
            for (int j : el)
            {
                if(dist[j].first==-1) dist[j].first = INF;
                if(dist[j].second==-1) dist[j].second = INF;
                r = min(r, max(dist[j].first, dist[j].second));
            }
            comp.push_back({d, r});

        }
    }
    sort(comp.begin(), comp.end(), cmp);
    long long res = 0;
    for (auto x : comp) res = max(res, x.first);
    res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));

    //for (auto x : comp) //cout<< x.first<<" "<<x.second<<endl;


    return res;

}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:138:47: error: no matching function for call to 'max(long long int&, int&)'
  138 |     for (auto x : comp) res = max(res, x.first);
      |                                               ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 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:138:47: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  138 |     for (auto x : comp) res = max(res, x.first);
      |                                               ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 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:138:47: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  138 |     for (auto x : comp) res = max(res, x.first);
      |                                               ^
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:138:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  138 |     for (auto x : comp) res = max(res, x.first);
      |                                               ^
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:138:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  138 |     for (auto x : comp) res = max(res, x.first);
      |                                               ^
dreaming.cpp:139:91: error: no matching function for call to 'max(long long int&, const int&)'
  139 |     res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));
      |                                                                                           ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 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:139:91: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  139 |     res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));
      |                                                                                           ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 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:139:91: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  139 |     res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));
      |                                                                                           ^
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:139:91: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  139 |     res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));
      |                                                                                           ^
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:139:91: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  139 |     res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));
      |                                                                                           ^