이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |