제출 #837552

#제출 시각아이디문제언어결과실행 시간메모리
837552tengiz05수천개의 섬 (IOI22_islands)C++17
27.75 / 100
45 ms4420 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; std::variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V) { if (n == 2) { vector<int> e[n]; for (int i = 0; i < m; i++) { e[U[i]].push_back(i); } if (e[0].size() >= 2 && e[1].size() >= 1) { return vector<int>{e[0][0], e[1][0], e[0][1], e[0][0], e[1][0], e[0][1]}; } else { return false; } } vector<vector<int>> adj(n); for (int i = 0; i < m; i++) { adj[U[i]].push_back(i); } if (adj[0].size() >= 2) { int a = adj[0][0]; int b = adj[0][1]; return vector<int>{a, a ^ 1, b, b ^ 1, a ^ 1, a, b ^ 1, b}; } vector<int> path; vector<bool> vis(n); vector<int> ans; bool found = false; function<void(int)> dfs = [&](int u) { vis[u] = true; if (adj[u].size() >= 3) { found = true; adj[u].erase(find(adj[u].begin(), adj[u].end(), path.back() ^ 1)); int a = adj[u][0]; int b = adj[u][1]; ans = path; vector<int> inter = {a, a ^ 1, b, b ^ 1, a ^ 1, a, b ^ 1, b}; ans.insert(ans.end(), inter.begin(), inter.end()); ans.insert(ans.end(), path.rbegin(), path.rend()); return; } for (int i : adj[u]) { if (vis[V[i]]) { continue; } path.push_back(i); dfs(V[i]); if (found) return; path.pop_back(); } }; dfs(0); if (ans.empty()) { return false; } else { 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...