Submission #837598

#TimeUsernameProblemLanguageResultExecution timeMemory
837598tengiz05Thousands Islands (IOI22_islands)C++17
29 / 100
27 ms4432 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 += 2) { adj[U[i]].push_back(i); } vector<int> path; vector<int> dep(n); vector<int> vis(n); bool found = false; vector<int> ans; function<void(int)> dfs = [&](int u) { vis[u] = 1; for (int i : adj[u]) { if (vis[V[i]] == 2) { continue; } if (vis[V[i]] == 1) { vector<int> cycle; for (int j = 0; j < dep[u] - dep[V[i]]; j++) { cycle.push_back(path.back()); path.pop_back(); } reverse(cycle.begin(), cycle.end()); cycle.push_back(i); for (int x : path) { ans.push_back(x); } for (int x : cycle) { ans.push_back(x); } for (int x : cycle) { ans.push_back(x ^ 1); } reverse(cycle.begin(), cycle.end()); for (int x : cycle) { ans.push_back(x); } for (int x : cycle) { ans.push_back(x ^ 1); } reverse(path.begin(), path.end()); for (int x : path) { ans.push_back(x); } found = true; return; } dep[V[i]] = dep[u] + 1; path.push_back(i); dfs(V[i]); if (found) return; path.pop_back(); } vis[u] = 2; }; 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...