Submission #842489

#TimeUsernameProblemLanguageResultExecution timeMemory
842489CodePlatinaLongest Trip (IOI23_longesttrip)C++17
30 / 100
790 ms1864 KiB
#include "longesttrip.h" #include <iostream> #include <algorithm> #define pii pair<int, int> #define ff first #define ss second using namespace std; vector<int> gph[404]; vector<int> longest_trip(int N, int d) { for(int i = 0; i < N; ++i) gph[i].clear(); for(int i = 0; i < N; ++i) { for(int j = i + 1; j < N; ++j) { if(!are_connected(vector<int>{i}, vector<int>{j})) { gph[i].push_back(j); gph[j].push_back(i); } } } for(int i = 0; i < N; ++i) if((int)gph[i].size() >= (N + 1) / 2) return gph[i]; for(int i = 0; i < N; ++i) sort(gph[i].begin(), gph[i].end()); bool chc[N]{}; vector<int> ret; ret.push_back(0), chc[0] = true; while(1) { bool flag = false; for(int i = 0; i < N; ++i) if(!chc[i] && !binary_search(gph[ret.back()].begin(), gph[ret.back()].end(), i)) { ret.push_back(i); chc[i] = true; flag = true; break; } if(!flag) break; } return ret; }
#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...