제출 #628076

#제출 시각아이디문제언어결과실행 시간메모리
628076amunduzbaev수천개의 섬 (IOI22_islands)C++17
5 / 100
1137 ms937124 KiB
#include "islands.h" #include "bits/stdc++.h" using namespace std; #include <variant> #ifndef EVAL #include "grader.cpp" #endif #define ar array const int N = 1e5 + 5; vector<int> edges[N]; int used[N], in[N]; variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v) { map<ar<int, 2>, int> id; vector<int> r(m); for(int i=0;i<m;i++){ edges[u[i]].push_back(i); if(id.count({v[i], u[i]})){ int j = id[{v[i], u[i]}]; r[j] = i, r[i] = j; } id[{u[i], v[i]}] = i; } if(edges[0].size() > 1){ int a = edges[0][0], b = edges[0][1]; return (vector<int>){a, r[a], b, r[b], r[a], a, r[b], b}; } vector<int> par(n, -1), is(n); queue<int> q; for(int i=0;i<n;i++){ if(edges[i].size() > 2){ is[i] = 1; q.push(i); } } while(!q.empty()){ int u = q.front(); q.pop(); for(auto x : edges[u]){ if(!is[v[x]]){ is[v[x]] = 1; par[v[x]] = x ^ 1; q.push(v[x]); } } } if(!is[0]) return false; vector<int> t; int x = 0; while(~par[x]){ t.push_back(par[x]); x = v[par[x]]; } int a = edges[x][0], b = edges[x][1]; if(a == (t.back() ^ 1)) a = edges[x][2]; if(b == (t.back() ^ 1)) b = edges[x][2]; assert(a != b && a != t.back() && b != t.back()); vector<int> res = t, tmp = {a, a ^ 1, b, b ^ 1, a ^ 1, a, b ^ 1, b}; res.insert(res.end(), tmp.begin(), tmp.end()); reverse(t.begin(), t.end()); res.insert(res.end(), t.begin(), t.end()); vector<int> cnt(m); for(int i=0;i<(int)res.size();i++){ //~ if(i){ //~ assert(u[res[i-1]] == u[res[i]]); //~ } swap(u[i], v[i]); cnt[i] ^= 1; } for(int i=0;i<m;i++){ assert(!cnt[i]); } return res; } /* 5 8 0 1 1 0 1 2 2 1 2 3 3 2 2 4 4 2 */
#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...