Submission #1240763

#TimeUsernameProblemLanguageResultExecution timeMemory
1240763SalihSahinLongest Trip (IOI23_longesttrip)C++20
0 / 100
8 ms448 KiB
#include "bits/stdc++.h" #include "longesttrip.h" #define pb push_back using namespace std; vector<int> longest_trip(int N, int D){ if(D == 1){ vector<vector<int> > paths; for(int i = 0; i < N; i++){ paths.pb({i}); } while(paths.size() > 2){ vector<vector<int> > npaths; for(int i = 0; i + 2 < paths.size(); i += 3){ int a = paths[i][0], b = paths[i+1][0], c = paths[i+2][0]; bool c1 = are_connected({a}, {b}); bool c2 = are_connected({a}, {c}); bool c3 = are_connected({b}, {c}); if(c1){ vector<int> v = paths[i]; reverse(v.begin(), v.end()); for(auto itr: paths[i+1]) v.pb(itr); npaths.pb(v); npaths.pb(paths[i+2]); } else if(c2){ vector<int> v = paths[i]; reverse(v.begin(), v.end()); for(auto itr: paths[i+2]) v.pb(itr); npaths.pb(v); npaths.pb(paths[i+1]); } else if(c3){ vector<int> v = paths[i+1]; reverse(v.begin(), v.end()); for(auto itr: paths[i+2]) v.pb(itr); npaths.pb(v); npaths.pb(paths[i]); } else{ abort(); } } if(paths.size() % 3 >= 1){ npaths.pb(paths[paths.size()-1]); } if(paths.size() % 3 >= 2){ npaths.pb(paths[paths.size()-2]); } paths = npaths; } bool check = are_connected(paths[0], paths[1]); if(paths[1].size() > paths[0].size()) swap(paths[0], paths[1]); if(!check){ return paths[0]; } else{ if(paths[1].size() == 1){ int a = paths[0][0], b = paths[0].back(), c = paths[1][0]; bool c1 = are_connected({a}, {b}); bool c2 = are_connected({b}, {c}); bool c3 = are_connected({c}, {a}); if(c3){ paths[0].pb(c); return paths[0]; } if(c2){ reverse(paths[0].begin(), paths[0].end()); paths[0].pb(c); return paths[0]; } int x = 0; for(auto itr: paths[0]){ if(are_connected({itr}, {c})){ x = itr; break; } } vector<int> updpath; for(auto itr: paths[0]){ updpath.pb(itr); if(itr == x) break; } updpath.pb(c); reverse(updpath.begin(), updpath.end()); reverse(paths[0].begin(), paths[0].end()); for(auto itr: paths[0]){ if(itr == x) break; updpath.pb(itr); } return paths[0]; } else{ int a = paths[0][0], b = paths[0].back(), c = paths[1][0], d = paths[1][1]; bool c1 = are_connected({a}, {b}); bool c2 = are_connected({b}, {c}); bool c3 = are_connected({c}, {a}); if(c2){ vector<int> v = paths[0]; for(auto itr: paths[1]) v.pb(itr); return v; } if(c3){ vector<int> v = paths[0]; reverse(v.begin(), v.end()); for(auto itr: paths[1]) v.pb(itr); return v; } bool c4 = are_connected({c}, {d}); bool c5 = are_connected({a}, {d}); bool c6 = are_connected({b}, {d}); if(c5){ vector<int> v = paths[0]; reverse(v.begin(), v.end()); reverse(paths[1].begin(), paths[1].end()); for(auto itr: paths[1]) v.pb(itr); return v; } if(c6){ vector<int> v = paths[1]; reverse(paths[0].begin(), paths[0].end()); for(auto itr: paths[0]) v.pb(itr); return v; } // şimdi cycle olduğunu biliyoruz pair<int, int> p = {-1, -1}; for(auto itr: paths[0]){ for(auto itr2: paths[1]){ if(are_connected({itr}, {itr2})){ p = {itr, itr2}; break; } } if(p.first != -1) break; } vector<int> ans; for(auto itr: paths[0]){ if(itr == p.first) break; ans.pb(itr); } reverse(ans.begin(), ans.end()); reverse(paths[0].begin(), paths[0].end()); for(auto itr: paths[0]){ ans.pb(itr); if(itr == p.first) break; } // son eleman p.first vector<int> ans2; for(auto itr: paths[1]){ if(itr == p.second) break; ans2.pb(itr); } reverse(ans2.begin(), ans2.end()); reverse(paths[1].begin(), paths[1].end()); for(auto itr: paths[1]){ ans2.pb(itr); if(itr == p.second) break; } // son eleman p.second vector<int> v = ans; reverse(ans2.begin(), ans2.end()); for(auto itr: ans2) v.pb(itr); return v; } } } return {}; }
#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...