Submission #1240460

#TimeUsernameProblemLanguageResultExecution timeMemory
1240460mychecksedadLongest Trip (IOI23_longesttrip)C++17
60 / 100
172 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); if(B.empty()) return A; int x = B[0], y = B.back(); int x1 = A[0], y1 = A.back(); bool ok = ask(x, x1); bool ok1 = ask(x, y1); if(ok){ reverse(all(A)); for(int x: B) A.pb(x); return A; } if(ok1){ for(int x: B) A.pb(x); return A; } ok = ask(y, x1); ok1 = ask(y, y1); if(ok){ for(int x: A) B.pb(x); return B; } if(ok1){ reverse(all(A)); for(int x: A) B.pb(x); return B; } // we got two loops for(int i = 0; i < B.size(); ++i){ for(int j = 0; j < A.size(); ++j){ if(ask(B[i], A[j])){ vi res; for(int k = i + 1; k < B.size(); ++k) res.pb(B[k]); for(int k = 0; k <= i; ++k) res.pb(B[k]); for(int k = j; k < A.size(); ++k) res.pb(A[k]); for(int k = 0; k < j; ++k) res.pb(A[k]); return res; } } } 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...