제출 #1042483

#제출 시각아이디문제언어결과실행 시간메모리
1042483yanb수천개의 섬 (IOI22_islands)C++17
10.85 / 100
18 ms6744 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define pii pair<int, int> union Ans { bool b; vector<int> v; Ans(bool b) : b(b) {} Ans(vector<int> v) : v(v) {} ~Ans() {} Ans(const Ans&) {} }; Ans n2(int n, int M, vector<int> U, vector<int> V) { vector<int> u0, u1; for (int i = 0; i < M; i++) { if (U[i]) u1.push_back(i); else u0.push_back(i); } if (u1.size() > 0 && u0.size() > 1) { vector<int> ans = {u0[0], u1[0], u0[1], u0[0], u1[0], u0[1]}; return ans; } else { return false; } } void dfs(int v, int p, vector<vector<pii>> &g, vector<bool> &uu, vector<int> &ps) { if (uu[v]) return; uu[v] = 1; ps[v] = p; for (auto [u, _] : g[v]) { dfs(u, v, g, uu, ps); } } Ans undirected(int n, int M, vector<int> U, vector<int> V) { vector<vector<pii>> g(n); for (int i = 0; i < M; i++) { g[U[i]].push_back({V[i], i}); } if (g[0].size() > 1) { int u = g[0][0].first, v = g[0][1].first; if (u == v) { vector<int> ans = {g[0][0].second, g[u][0].second, g[0][1].second, g[0][0].second, g[u][0].second, g[0][1].second}; return ans; } vector<int> ans = {g[0][0].second, g[u][0].second, g[0][1].second, g[v][0].second, g[u][0].second, g[0][0].second, g[v][0].second, g[0][1].second}; return true; } vector<bool> uu(n); vector<int> p(n); dfs(0, 0, g, uu, p); for (int i = 0; i < n; i++) { if (g[i].size() > 2 && uu[i]) return true; } return false; } Ans find_journey(int n, int M, vector<int> U, vector<int> V) { if (n == 2) return n2(n, M, U, V); return undirected(n, M, U, V); } #ifdef ONLINE_JUDGE signed main() { Ans ans = find_journey(3, 4, {0, 1, 1, 0}, {1, 0, 0, 1}); if (ans.b) { for (int x : ans.v) cout << x << " "; cout << "\n"; } } #endif
#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...