Submission #335981

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

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;

const int MAXN = 1e5 + 5, INF = 1e9 + 5;
using ll = long long;

vector<pair<int, int>> g[MAXN];
vector<pair<int, int>> bestComps;
bool vis[MAXN];
pair<int, int> leaf[2];
pair<int, int> optimalRoot;
int diameterDist[MAXN][2];

void diameter(int u, int p, int dist, int idx) {
    vis[u] = true;

    leaf[idx] = max(leaf[idx], make_pair(dist, u));
    diameterDist[u][idx] = dist;

    optimalRoot = min(optimalRoot, make_pair(max(diameterDist[u][0], diameterDist[u][1]), u));

    for (const auto &[v, wt] : g[u]) {
        if (v == p) continue;
        dfs(v, u, dist + wt, idx);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }

    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;

        leaf[0] = leaf[1] = {-INF, -INF};

        diameter(u, -1, 0, 0);
        diameter(leaf[0].second, -1, 0, 1);
        optimalRoot = {INF, u};
        diameter(leaf[1].second, -1, 0, 0);

        bestComps.emplace_back(optimalRoot.first, optimalRoot.second);
    }

    sort(bestComps.begin(), bestComps.end(), greater<>());

    int best = bestComps.front().second;
    
    for (int i = 1; i < int(bestComps.size()); i++) {
        int v = bestComps[i].second;

        g[best].emplace_back(v, L);
        g[v].emplace_back(best, L);
    }

    leaf[0] = leaf[1] = {-INF, -INF};

    diameter(0, -1, 0, 0);
    diameter(leaf[0].second, -1, 0, 1);

    return leaf[1].first;
}

Compilation message (stderr)

dreaming.cpp: In function 'void diameter(int, int, int, int)':
dreaming.cpp:27:9: error: 'dfs' was not declared in this scope; did you mean 'ffs'?
   27 |         dfs(v, u, dist + wt, idx);
      |         ^~~
      |         ffs
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:42:18: error: 'u' was not declared in this scope
   42 |         diameter(u, -1, 0, 0);
      |                  ^
dreaming.cpp:44:30: error: no match for 'operator=' (operand types are 'std::pair<int, int>' and '<brace-enclosed initializer list>')
   44 |         optimalRoot = {INF, u};
      |                              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from dreaming.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:378:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch_no_braces&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch_no_braces&>::type = const std::pair<int, int>&]'
  378 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:381:51: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<int, int>&, const std::__nonesuch_no_braces&>::type' {aka 'const std::pair<int, int>&'}
  378 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~              
  379 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~                  
  380 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
  381 |   const pair&, const __nonesuch_no_braces&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_pair.h:389:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch_no_braces&&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch_no_braces&&>::type = std::pair<int, int>&&]'
  389 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:392:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<int, int>&&, std::__nonesuch_no_braces&&>::type' {aka 'std::pair<int, int>&&'}
  389 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  390 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  391 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  392 |   pair&&, __nonesuch_no_braces&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_pair.h:405:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  405 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:405:2: note:   template argument deduction/substitution failed:
dreaming.cpp:44:30: note:   couldn't deduce template parameter '_U1'
   44 |         optimalRoot = {INF, u};
      |                              ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from dreaming.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:416:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  416 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:416:2: note:   template argument deduction/substitution failed:
dreaming.cpp:44:30: note:   couldn't deduce template parameter '_U1'
   44 |         optimalRoot = {INF, u};
      |                              ^