제출 #807493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
807493		Ozy	수천개의 섬 (IOI22_islands)	C++17	22.75 / 100	29 ms	8060 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<lli> ciclo;
vector<pll> hijos[MAX+2];

bool dfs(lli pos){
  vis[pos] = 1;

  lli cont = 0;
  pll a = {-1,-1};
  pll b = {-1,-1};
  for(auto h : hijos[pos]) {
    if(vis[h.des]) continue;
    cont++;
    if (a.des == -1) a = h;
    else b = h;
  }

  if(cont == 0) return false;
  else if(cont == 1) {
    camino.push_back(a.id);
    if(dfs(a.des)) {
      camino.push_back(a.id);
      return true;
    }
    else return false;
  }
  else {
    lli w,x,y,z;
    w = a.id;
    x = (a.id^1);    
    y = b.id;
    z = (b.id^1);
  
    camino.push_back(w);
    camino.push_back(x);
    camino.push_back(y);
    camino.push_back(z);
  
    camino.push_back(x);
    camino.push_back(w);
    camino.push_back(z);
    camino.push_back(y);
    return true;
  }

}

//solucion para la subtask #3
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});
    hijos[V[i]].push_back({U[i],i+1});
  }

  if (dfs(0)) return camino;
  else return false;
}

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