Submission #1240132

#TimeUsernameProblemLanguageResultExecution timeMemory
1240132vako_pLongest Trip (IOI23_longesttrip)C++20
5 / 100
325 ms440 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define sd second #define debug(x) cerr << #x << "----> " << x << endl; //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("O3") int n; void dfs(ll at, vector<vector<bool>> &edge, vector<int> &ans, vector<bool> &vis){ ans.pb(at); vis[at] = true; for(int i = 0; i < n; i++){ if(at == i or !edge[at][i] or vis[i]) continue; dfs(i, edge, ans, vis); } } std::vector<int> longest_trip(int N, int D){ n = N; vector<vector<bool>> edge(n + 5, vector<bool>(n + 5, false)); vector<int> v(n + 5, 0LL); for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(!are_connected({i}, {j})) continue; v[i]++; v[j]++; edge[i][j] = edge[j][i] = true; } } vector<int> ans; ll sz = (n + 1) / 2; for(int i = 0; i < n; i++){ if(v[i] < sz - 1){ for(int j = 0; j < n; j++){ if(i == j or edge[i][j]) continue; ans.pb(j); } return ans; } } vector<bool> vis(n + 5, false); dfs(0, edge, ans, vis); assert(ans.size() >= (n + 1) / 2); return ans; }
#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...