# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
633219 | tutis | 수천개의 섬 (IOI22_islands) | C++17 | 131 ms | 15300 KiB |
이 제출은 이전 버전의 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);
auto c = [&](int s)->pair<vector<int>, vector<int>>
{
vector<int> D(N, -1);
D[s] = 0;
int t = V[adj[s][0]];
vector<int>v = {adj[s][0]};
int val = 0;
while (D[t] == -1)
{
val++;
D[t] = val;
v.push_back(adj[t][0]);
t = V[adj[t][0]];
}
vector<int>a, b;
for (int i = 0; i < D[t]; i++)
a.push_back(v[i]);
for (int i = D[t]; i < (int)v.size(); i++)
b.push_back(v[i]);
return {a, b};
};
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 == 0 && 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(0, -1);
reverse(ans0.begin(), ans0.end());
for (int i : ans0)
ret.push_back(i);
return ret;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |