Submission #957226

#	Time	Username	Problem	Language	Result	Execution time	Memory
957226		Nelt	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	810 ms	2260 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];
bool mat[N][N];
std::vector<int> longest_trip(int n, int d)
{
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < n; j++)
            mat[i][j] = 0;
    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), mat[i][j] = mat[j][i] = true;
    if (d == 2)
    {
        vector<int> ans;
        ll found = 0;
        for (ll i = 0; i + 1 < n; i++)
            if (mat[i][i + 1])
            {
                ans.push_back(i), ans.push_back(i + 1), found = i;
                break;
            }
        for (ll i = 0; i < n; i++)
            if (i != found and i != found + 1)
            {
                if (mat[ans.front()][i])
                    ans.insert(ans.begin(), i);
                else
                    ans.push_back(i);
            }
        return ans;
    }
    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;
        }
    }
    return ans;
}

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