Submission #1214596

#TimeUsernameProblemLanguageResultExecution timeMemory
1214596trimkusLongest Trip (IOI23_longesttrip)C++20
15 / 100
1101 ms525860 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; int N; const int MAXN = 256; vector<int> adj[MAXN]; void connect(vector<int>& path1, vector<int>& path2) { reverse(begin(path2), end(path2)); for (int j = 0; j < (int)path2.size(); ++j) { path1.push_back(path2[j]); } path2.clear(); } std::vector<int> longest_trip(int _N, int D) { N = _N; vector<int> idx(N); iota(begin(idx), end(idx), 0); mt19937 rng(0); // shuffle(begin(idx), end(idx), rng); vector<int> path1{idx[0]}, path2{idx[1]}; for (int j = 2; j < N; ++j) { int i = idx[j]; if (are_connected({path1.back()}, {i})) { path1.push_back(i); } else if (are_connected({path2.back()}, {i})) { path2.push_back(i); } else { assert(are_connected({path1.back()}, {path2.back()})); connect(path1, path2); path2.push_back(i); } } if (path1.size() < path2.size()) swap(path1, path2); if (path2.size() == 0) return path1; if (are_connected({path1.back()}, {path2.back()})) { connect(path1, path2); return path1; } reverse(begin(path1), end(path1)); if (are_connected({path1.back()}, {path2.back()})) { connect(path1, path2); return path1; } reverse(begin(path1), end(path1)); reverse(begin(path2), end(path2)); if (are_connected({path1.back()}, {path2.back()})) { connect(path1, path2); return path1; } reverse(begin(path1), end(path1)); if (are_connected({path1.back()}, {path2.back()})) { connect(path1, path2); return path1; } reverse(begin(path1), end(path1)); reverse(begin(path2), end(path2)); cerr << "Path1 = "; for (auto& u : path1) { cerr << u << " "; } cerr << "\nPath2 = "; for (auto& u : path2) { cerr << u << " "; } cerr << "\n"; if (N <= 20) { for (int i = 0; i < (int)path1.size(); ++i) { for (int j = 0; j < (int)path2.size(); ++j) { if (are_connected({path1[i]}, {path2[j]})) { cerr << "Found a connection = " << path1[i] << " " << path2[j] << "\n"; vector<int> super_path; int ni = (i + 1) % (int)path1.size(); while (ni != i) { super_path.push_back(path1[ni]); ni = (ni + 1) % (int)path1.size(); } super_path.push_back(path1[i]); super_path.push_back(path2[j]); int nj = (j + 1) % (int)path2.size(); while (nj != j) { super_path.push_back(path2[nj]); nj = (nj + 1) % (int)path2.size(); } cerr << "Cycle len = " << super_path.size() << "\n"; // reverse(begin(super_path), end(super_path)); return super_path; } } } return path1; } vector<int> super_path; int l1 = 0, r1 = (int)path1.size(); int l2 = 0, r2 = (int)path2.size(); while (r1 - l1 > 1) { int m1 = (l1 + r1) / 2; if (are_connected(vector<int>(begin(path1) + l1, begin(path1) + r1), vector<int>(begin(path2) + l2, begin(path2) + r2))) { r1 = m1; } else { l1 = m1; } } while (r2 - l2 > 1) { int m2 = (l2 + r2) / 2; if (are_connected(vector<int>(begin(path1) + l1, begin(path1) + r1), vector<int>(begin(path2) + l2, begin(path2) + r2))) { r2 = m2; } else { l2 = m2; } } int ni = (r1 + 1) % (int)path1.size(); while (ni != r1) { super_path.push_back(path1[ni]); ni = (ni + 1) % (int)path1.size(); } super_path.push_back(path1[r1]); super_path.push_back(path2[r2]); ni = (r2 + 1) % (int)path2.size(); while (ni != r2) { super_path.push_back(path2[ni]); ni = (ni + 1) % (int)path2.size(); } return super_path; }
#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...