제출 #736408

#제출 시각아이디문제언어결과실행 시간메모리
736408jk410수천개의 섬 (IOI22_islands)C++17
22.75 / 100
38 ms5192 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; int n; vector<pair<int, int>> edge[1000]; int deg[1000]; int par[1000]; bool visited[1000]; void dfs(int v) { visited[v] = true; for (auto i : edge[v]) { if (!visited[i.first]) { par[i.first] = v; dfs(i.first); } } } int f(int x) { if (x & 1) return x - 1; return x + 1; } variant<bool, vector<int>> find_journey(int _n, int m, vector<int> u, vector<int> v) { n = _n; memset(par, -1, sizeof(par)); for (int i = 0; i < m; i++) { edge[u[i]].push_back({ v[i],i }); deg[u[i]]++; } visited[0] = true; dfs(0); int x = -1; for (int i = 0; i < n; i++) { if (visited[i] && deg[i] > 2) x = i; } if (deg[0] > 1) x = 0; if (x == -1) return false; vector<int> p; for (int i = x;; i = par[i]) { p.push_back(i); if (!i) break; } vector<int> ret; for (int i = (int)p.size() - 1; i; i--) { for (auto j : edge[p[i]]) { if (j.first == p[i - 1]) { ret.push_back(j.second); break; } } } int sz = (int)ret.size(); pair<int, int> e1 = { -1,-1 }, e2 = { -1,-1 }; for (auto i : edge[x]) { if (ret.empty() || ret[sz - 1] != f(i.second)) { if (e1.second == -1) e1 = { i.second,f(i.second) }; else if (e2.second == -1) e2 = { i.second,f(i.second) }; } } ret.push_back(e1.first); ret.push_back(e1.second); ret.push_back(e2.first); ret.push_back(e2.second); ret.push_back(e1.second); ret.push_back(e1.first); ret.push_back(e2.second); ret.push_back(e2.first); for (int i = sz - 1; i >= 0; i--) ret.push_back(ret[i]); return ret; }
#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...