Submission #1065236

#TimeUsernameProblemLanguageResultExecution timeMemory
1065236LittleOrangeLongest Trip (IOI23_longesttrip)C++17
40 / 100
938 ms852 KiB
#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 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> ret; vector<ll> ord(n); iota(ord.begin(),ord.end(),0); vector<ll> cur; cur.reserve(n); ll cnt = 500000/max(n,10); while(cnt--){ shuffle(ord.begin(),ord.end(),mt); cur.push_back(ord[0]); for(ll i : ord){ if (a[cur.back()][i]) cur.push_back(i); } if(cur.size()>ret.size()) ret = cur; cur.clear(); } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...