Submission #914161

#	Time	Username	Problem	Language	Result	Execution time	Memory
914161		Nelt	Longest Trip (IOI23_longesttrip)	C++17	30 / 100	829 ms	2496 KiB

longesttrip

#include "longesttrip.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 256;
vv(ll) g[N];
std::vector<int> longest_trip(int n, int d)
{
    for (ll i = 0; i < n; i++)
        g[i].clear();
    vv(int) ans;
    if (d == 3)
    {
        for (ll i = 0; i < n; i++)
            ans.pb(i);
        return ans;
    }
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (are_connected({i}, {j}))
                g[i].pb(j), g[j].pb(i);
    if (d == 1)
    {
        ll v = 0;
        bool used[n];
        for (ll i = 0; i < n; i++)
            used[i] = 0;
        for (ll i = 0; i < n; i++)
            if (g[i].size() > g[v].size())
                v = i;
        while (v != -1)
        {
            used[v] = 1;
            ans.pb(v);
            ll to = -1;
            for (ll i : g[v])
                if (!used[i] and (to == -1 or g[i].size() > g[to].size()))
                    to = i;
            v = to;
        }
    }
    else
    {
        ll v = 0;
        bool used[n];
        for (ll i = 0; i < n; i++)
            used[i] = 0;
        for (ll i = 0; i < n; i++)
            if (g[i].size() == n - 2)
                v = i;
        while (v != -1)
        {
            used[v] = 1;
            ans.pb(v);
            ll to = -1;
            for (ll i : g[v])
                if (!used[i] and (to == -1 or g[i].size() > g[to].size()))
                    to = i;
            v = to;
        }
    }
    return ans;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:89:29: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |             if (g[i].size() == n - 2)
      |                 ~~~~~~~~~~~~^~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60