제출 #807521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807521		Ozy	수천개의 섬 (IOI22_islands)	C++17	0 / 100	33 ms	5948 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#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 pll pair<lli,lli>

#define MAX 1000
//para el vector de hijos
#define des first
#define id second

vector<int> camino;
lli a,b,c,d,n;
lli vis[MAX+2];
stack<pll> pila;
vector<pll> hijos[MAX+2];

bool dfs(lli pos,lli rama){
  if(rama != -1) {
    pila.push({pos,rama});
    camino.push_back(rama);
  }

  if (vis[pos] == 1) { //estoy en un ciclo

    vector<lli> orden;
    orden.push_back(rama);
    pila.pop();

    while (!pila.empty() && pila.top().des != pos) {
      orden.push_back(pila.top().id);
      vis[pila.top().des] = 2;
      pila.pop();
    }
    
    reverse(orden.begin(), orden.end());
    for(auto act : orden) camino.push_back(act^1);

    reverse(orden.begin(), orden.end());
    for(auto act : orden) camino.push_back(act);
    for(auto act : orden) camino.push_back(act^1);

    return true;
  }

  vis[pos] = 1;
  bool puedo = false;
  for (auto h : hijos[pos]) {
    if(dfs(h.des,h.id)) {
      puedo = true;
      break;
    }
  }

  if (!puedo) {
    if (rama != -1) {
      pila.pop();
      camino.pop_back();
    }
    return false;
  }
  if (vis[pos] == 1 && rama >= 0) camino.push_back(rama);
  return true;
}

//solucion para la subtask #4
std::variant<bool, std::vector<int>> find_journey( int N, int M, std::vector<int> U, std::vector<int> V) {
  n = N;

  rep(i,0,M-1) {
    if(i&1) continue;
    hijos[U[i]].push_back({V[i],i});
  }

  if (dfs(0,-1)) return camino;
  else return false;
}
//que no se te olvide sacar de la pila

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45