Submission #1192602

#TimeUsernameProblemLanguageResultExecution timeMemory
1192602catch_me_if_you_canLongest Trip (IOI23_longesttrip)C++20
85 / 100
7 ms420 KiB
#include<bits/stdc++.h> #include "longesttrip.h" using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back bool c_edge(int u, int v) { return are_connected({u}, {v}); } vector<int> longest_trip(int n, int d) { vector<int> v1; vector<int> v2; for(int i = 0; i < n; i++) { if(v1.empty()) { v1.pb(i); continue; } if(v2.empty()) { v2.pb(i); continue; } if(c_edge(v1.back(), i)) { v1.pb(i); continue; } if(c_edge(v2.back(), i)) { v2.pb(i); continue; } while(v1.size()) { v2.pb(v1.back()); v1.pob(); } v1.pb(i); } if(c_edge(v1.back(), v2.back())) { while(v1.size()) { v2.pb(v1.back()); v1.pob(); } return v2; } if(c_edge(v1.front(), v2.back())) { reverse(v1.begin(), v1.end()); while(v1.size()) { v2.pb(v1.back()); v1.pob(); } return v2; } reverse(v2.begin(), v2.end()); if(c_edge(v1.back(), v2.back())) { while(v1.size()) { v2.pb(v1.back()); v1.pob(); } return v2; } if(c_edge(v1.front(), v2.back())) { reverse(v1.begin(), v1.end()); while(v1.size()) { v2.pb(v1.back()); v1.pob(); } return v2; } if(v1.empty()) return v2; if(v2.empty()) return v1; if(v1.size() > v2.size()) swap(v1, v2); if(!are_connected(v1, v2)) return v2; int l = 0; int r = v2.size()-1; while(l < r) { int m = (l+r)/2; vector<int> s = v2; s.resize(m+1); if(are_connected(v1, s)) r = m; else l = m+1; } int S2 = l;//v2[S] is target. l = 0; r = v1.size()-1; while(l < r) { int m = (l+r)/2; vector<int> s = v1; s.resize(m+1); if(are_connected({v2[S2]}, s)) r = m; else l = m+1; } int S1 = l; //v1[S1], v2[S2] are connected. //(n-1-S1) vector<int> pth; for(int i = S1-1; i >= 0; i--) pth.pb(v1[i]); for(int i = v1.size()-1; i >= S1; i--) pth.pb(v1[i]); for(int i = S2; i < v2.size(); i++) pth.pb(v2[i]); for(int i = 0; i < S2; i++) pth.pb(v2[i]); return pth; }
#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...