Submission #1065228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065228		LittleOrange	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	1033 ms	852 KiB

longesttrip

#include "longesttrip.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;

std::vector<int> longest_trip(int N, int D)
{
    mt19937_64 mt(random_device{}());
    ll t0 = time(0);
    ll n = N;
    if (D==3){
        vector<ll> r(n);
        iota(r.begin(),r.end(),0);
        return r;
    }
    vector<vector<ll>> a(n,vector<ll>(n,0));
    for(ll i = 0;i<n;i++){
        for(ll j = i+1;j<n;j++){
            a[i][j] = a[j][i] = are_connected({i},{j});
        }
    }
    vector<ll> vis(n,0);
    vector<ll> ret;
    vector<ll> ord(n);
    iota(ord.begin(),ord.end(),0);
    auto it = ord.begin();
    vector<ll> cur;
    function<void(ll)> dfs;
    dfs = [&](ll i){
        cur.push_back(i);
        vis[i] = 1;
        for(;it!=ord.end();it++){
            ll j = *it;
            if(a[i][j]&&!vis[j]){
                dfs(j);
                return;
            }
        }
    };
    ll cnt = 10000;
    while(cnt--){
        shuffle(ord.begin(),ord.end(),mt);
        it = ord.begin();
        dfs(ord[0]);
        if(cur.size()>ret.size()) ret = cur;
        cur.clear();
        fill(vis.begin(),vis.end(),0);
    }
    return ret;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:11:8: warning: unused variable 't0' [-Wunused-variable]
   11 |     ll t0 = time(0);
      |        ^~

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