Submission #1056465

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1056465	2024-08-13T09:34:00 Z	Ignut	Longest Trip (IOI23_longesttrip)	C++17	Compilation error	0 ms	0 KB

longesttrip

/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

mt19937 rnd(11223344);

bool are_connected(vector<int> A, vector<int> B);

const int MAXN = 333;

vector<int> g[MAXN];
bool used[MAXN];

vector<int> order;

void dfs(int v) {
    order.push_back(v);
    used[v] = true;
    for (int to : g[v]) {
        if (used[to]) continue;
        dfs(to);
        return;
    }
}

vector<int> longest_trip(int N, int D) {
    if (D == 3) {
        vector<int> vec;
        for (int i = 0; i < N; i ++) vec.push_back(i);
        return vec;
    }
    if (D == 2) {
        vector<pair<int, int>> lst;
        int cnt[N] = {};
        for (int i = 0; i < N; i ++) {
            for (int j = i + 1; j < N; j ++) {
                if (!are_connected({i}, {j})) {
                    lst.push_back({i, j});
                    cnt[i] ++, cnt[j] ++;
                }
            }
        }
        vector<int> free;
        for (int i = 0; i < N; i ++) if (cnt[i] == 0) free.push_back(i);
        vector<int> res;
        for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].first);
        for (int val : free) res.push_back(val);
        for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].second);
        return res;
    }

    order.clear();
    for (int i = 0; i < N; i ++) {
        g[i].clear();
        used[i] = false;
    }

    for (int i = 0; i < N; i ++) {
        for (int j = i + 1; j < N; j ++) {
            if (are_connected({i}, {j})) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    for (int i = 0; i < N; i ++) {
        shuffle(g[i].begin(), g[i].end(), rnd());
    }

    vector<int> res;
    for (int start = 0; start < N; start ++) {
        for (int i= 0; i < N; i ++) used[i] = false;
        order.clear();
        dfs(start);
        if (order.size() > res.size()) res = order;
    }
    return res;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].first);
      |                         ~~^~~~~~~~~~~~
longesttrip.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i < lst.size(); i ++) res.push_back(lst[i].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 longesttrip.cpp:28:
/usr/include/c++/10/bits/stl_algo.h: In instantiation of 'void std::shuffle(_RAIter, _RAIter, _UGenerator&&) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _UGenerator = long unsigned int]':
longesttrip.cpp:96:48:   required from here
/usr/include/c++/10/bits/stl_algo.h:3769:2: error: 'std::remove_reference<long unsigned int>::type' {aka 'long unsigned int'} is not a class, struct, or union type
 3769 |  __uc_type;
      |  ^~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3797:37: error: 'std::remove_reference<long unsigned int>::type' {aka 'long unsigned int'} is not a class, struct, or union type
 3797 |    const pair<__uc_type, __uc_type> __pospos =
      |                                     ^~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3797:37: error: 'std::remove_reference<long unsigned int>::type' {aka 'long unsigned int'} is not a class, struct, or union type