| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 826128 | LittleCube | 수천개의 섬 (IOI22_islands) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "islands.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
namespace
{
int K;
vector<int> path;
int vis[100000], use[200000], p[100000], pe[100000], deg[100000];
vector<pii> E[100000];
void dfs(int u)
{
vis[u] = 1;
for (auto [v, i] : E[u])
if (vis[v] == 0)
{
p[v] = u;
pe[v] = i;
dfs(v);
deg[u]++;
}
else if (vis[v] == 1 && i != pe[u] ^ 1)
use[i] = 1;
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
for (int i = 0; i < M; i++)
E[U[i]].emplace_back(pii(V[i], i));
p[0] = -1;
dfs(0);
if (*max_element(deg, deg + N) >= 2)
{
int k = max_element(deg, deg + N) - deg;
vector<int> down, branch, sol;
for (int i = 0; i < N; i++)
if(p[i] == k)
branch.emplace_back(pe[i]);
while(k)
{
down.emplace_back(pe[k]);
k = p[k];
}
reverse(down.begin(), down.end());
sol.insert(sol.end(), down.begin(), down.end());
for (int i : branch)
sol.emplace_back(i), sol.emplace_back(i ^ 1);
for (int i : branch)
sol.emplace_back(i ^ 1), sol.emplace_back(i);
reverse(down.begin(), down.end());
for (int i : down)
sol.emplace_back(i ^ 1);
return true
}
if (*max_element(use, use + M) >= 1)
return true;
return false;
}