제출 #823619

#제출 시각아이디문제언어결과실행 시간메모리
823619finn__수천개의 섬 (IOI22_islands)C++17
24 / 100
76 ms19020 KiB
#include <bits/stdc++.h> #include "islands.h" using namespace std; constexpr size_t N_MAX = 100000; set<pair<int, int>> g[N_MAX]; bitset<N_MAX> visited, in_dfs; int find_cycle(int u, vector<int> &cycle, vector<int> &path_to_cycle) { if (in_dfs[u]) return u; if (visited[u]) return -1; in_dfs[u] = 1; visited[u] = 1; for (auto const &[v, i] : g[u]) { int x = find_cycle(v, cycle, path_to_cycle); if (x != -1) { cycle.push_back(i); return x == u ? -1 : x; } else if (!cycle.empty()) { path_to_cycle.push_back(i); return -1; } } in_dfs[u] = 0; return -1; } variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { for (int i = 0; i < M; ++i) g[U[i]].emplace(V[i], i); vector<int> cycle, path_to_cycle; find_cycle(0, cycle, path_to_cycle); if (cycle.empty()) return false; reverse(cycle.begin(), cycle.end()); reverse(path_to_cycle.begin(), path_to_cycle.end()); vector<int> tour = path_to_cycle; tour.insert(tour.end(), cycle.begin(), cycle.end()); for (size_t i = path_to_cycle.size(); i < path_to_cycle.size() + cycle.size(); ++i) { if (tour[i] + 1 < M && U[tour[i]] == U[tour[i] + 1] && V[tour[i]] == V[tour[i] + 1]) tour.push_back(tour[i] + 1); else tour.push_back(tour[i] - 1); } tour.resize(tour.size() * 2); copy(tour.begin() + path_to_cycle.size(), tour.begin() + tour.size() / 2, tour.begin() + tour.size() / 2); copy(path_to_cycle.begin(), path_to_cycle.end(), tour.end() - path_to_cycle.size()); reverse(tour.begin() + tour.size() / 2, tour.begin() + tour.size() / 2 + cycle.size()); reverse(tour.begin() + tour.size() / 2 + cycle.size(), tour.end() - path_to_cycle.size()); reverse(tour.end() - path_to_cycle.size(), tour.end()); return tour; }
#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...