Submission #1240442

#TimeUsernameProblemLanguageResultExecution timeMemory
1240442mychecksedadLongest Trip (IOI23_longesttrip)C++17
30 / 100
4 ms420 KiB
#include "longesttrip.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define pii pair<int,int> #define ff first #define ss second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rn(int l, int r){ return uniform_int_distribution<int>(l,r)(rng); } int ask(int u, int v){ return are_connected(vi{u}, vi{v}); } std::vector<int> longest_trip(int n, int D){ vi p; for(int i = 1; i <= n; ++i){ p.pb(i-1); swap(p[i-1], p[rn(0, i-1)]); } vi A, B; A.pb(p[0]); for(int i = 1; i < n; ++i){ int v = p[i]; int u = A.back(); if(ask(u, v)){ A.pb(v); }else if(B.size()){ u = B.back(); if(ask(u, v)){ B.pb(v); }else{ reverse(all(B)); for(int x: B) A.pb(x); B.clear(); B.pb(v); } }else B.pb(v); } if(B.size()>A.size()) A.swap(B); return A; }
#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...