이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
int s = 0;
vector<bool> e(N, true);
vector<int>ans0;
{
vector<int> C(N, 0);
vector<int>b[N];
vector<int>ff[N];
for (int i = 0; i < M; i++)
{
C[U[i]]++;
b[V[i]].push_back(U[i]);
ff[U[i]].push_back(i);
}
stack<int>Q;
for (int i = 0; i < N; i++)
if (C[i] == 0)
Q.push(i);
while (e[s])
{
if (C[s] == 1)
{
int s_ = -1;
for (int ee : ff[s])
{
if (e[V[ee]])
{
ans0.push_back(ee);
s_ = V[ee];
}
}
for (int t : b[s])
{
if (e[t])
{
C[t]--;
if (C[t] == 0)
Q.push(t);
}
}
e[s] = false;
s = s_;
continue;
}
if (Q.empty())
break;
int a = Q.top();
Q.pop();
if (!e[a])
continue;
e[a] = false;
for (int t : b[a])
{
if (e[t])
{
C[t]--;
if (C[t] == 0)
Q.push(t);
}
}
}
if (!e[s])
return false;
}
vector<int>adj[N];
vector<int>adj_[N];
for (int i = 0; i < M; i++)
if (e[U[i]] && e[V[i]])
adj[U[i]].push_back(i);
// for (int i = 0; i < N; i++)
// if (i != s)
// while (adj[i].size() > 1)
// adj[i].pop_back();
// while (adj[s].size() > 2)
// adj[s].pop_back();
for (int i = 0; i < N; i++)
for (int e : adj[i])
{
adj_[V[e]].push_back(e);
}
vector<int>ret = ans0;
int ss = 0;
vector<bool> state(M, false);
bool fnd = false;
function<void(int, int)> dfs = [&](int i, int e)->void
{
if (i == s && e != -1 && ss == 0)
{
fnd = true;
return;
}
for (int ee : adj[i])
{
int j = V[ee];
if (e == ee || state[ee] == true)
continue;
state[ee] = true;
ret.push_back(ee);
ss++;
dfs(j, ee);
ss--;
if (fnd)
return;
ret.pop_back();
state[ee] = false;
}
for (int ee : adj_[i])
{
int j = U[ee];
if (e == ee || state[ee] == false)
continue;
state[ee] = false;
ss--;
ret.push_back(ee);
dfs(j, ee);
if (fnd)
return;
ss++;
ret.pop_back();
state[ee] = true;
}
};
dfs(s, -1);
reverse(ans0.begin(), ans0.end());
for (int i : ans0)
ret.push_back(i);
if (!fnd)
return false;
return ret;
}
# | 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... |