Submission #1078129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078129		idas	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	362 ms	1956 KiB

longesttrip

#include "bits/stdc++.h"
#include "longesttrip.h"

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, d;
map<pii, bool> mp;

bool con(int a, int b) {
    if(mp.count({a,b})) return mp[{a,b}];
    return mp[{a,b}]=are_connected({a},{b});
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

std::vector<int> longest_trip(int N, int D) {
    mp.clear();
    n=N; d=D;
    if(d==3) {
        vi ans;
        FOR(i, 0, n) ans.pb(i);
        return ans;
    }
    if(d==2) {
        vi ins;
        FOR(i, 0, n) ins.pb(i);

        shuffle(ins.begin(), ins.end(), rng);

        vi ans;
        int st=0;
        while(sz(ans)<n) {
            ans.clear();
            vector v(n, false);
            ans.pb(ins[st]); v[ins[st]]=true;
            FOR(z, 0, n-1) {
                FOR(j, 0, n) {
                    int i=ins[j];
                    if(v[i]) continue;
                    if(con(ans.back(), i)) {
                        ans.pb(i);
                        v[i]=true;
                        break;
                    }
                }
            }
            st++;
        }

        return ans;
    }

    vi ins;
    FOR(i, 0, n) ins.pb(i);

    shuffle(ins.begin(), ins.end(), rng);

    vi ans;
    int st=0;
    while(sz(ans)<(n+1)/2) {
        ans.clear();
        vector v(n, false);
        ans.pb(ins[st]); v[ins[st]]=true;
        FOR(z, 0, n-1) {
            FOR(j, 0, n) {
                int i=ins[j];
                if(v[i]) continue;
                if(con(ans.back(), i)) {
                    ans.pb(i);
                    v[i]=true;
                    break;
                }
            }
        }
        st++;
    }

    return ans;
}

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