| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 637464 | Ozy | 수천개의 섬 (IOI22_islands) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i < = (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define lli long long int
#define MAX 100000
#define des first
#define id second
int n,m;
vector<pair<int,int> > hijos[MAX];
vector<int> res;
bool solve(int pos,int padre) {
lli cont = 0;
pair<int,int> obj[2],regreso[2];
for (auto h : hijos[pos]){
if (h.des == padre) continue;
obj[cont] = h;
cont++;
if (cont == 2) break;
}
//tomar en cuenta que puede ser la misma balsa y estar usada
if (cont == 0) return false;
if (cont == 1) {
//caso en el cual sigues avanzando por ahi
res.push_back(obj[0].id);
if (solve(obj[0].des,pos) {
res.push_back(obj[0].id);
return true;
}
else {
res.pop_back();
return false;
}
}
//caso en el que tu empiezas a ser true
for (auto h : hijos[obj[0].des]) {
if (h.des == pos) {
regreso[0] = {pos,h.id};
break;
}
}
for (auto h : hijos[obj[1].des]) {
if (h.des == pos && h != regreso[0]) {
regreso[1] = {pos,h.id};
break;
}
}
//pon la secuencia
int a = obj[0].id;
int b = regreso[0].id;
int c = obj[1].id;
int d = regreso[1].id;
res.push_back(a);
res.push_back(b);
res.push_back(c);
res.push_back(d);
res.push_back(b);
res.push_back(a);
res.push_back(d);
res.push_back(c);
return true;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
n = N;
m = M;
rep(i,0,m-1) hijos[U[i]].push_back(V[i],i);
if (solve(0,-1)) return res;
else return false;
}