제출 #1320076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320076		madamadam3	Thousands Islands (IOI22_islands)	C++20	0 / 100	779 ms	1388120 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct state {
  int moves, cur, lst;
  vi steps, config;
};

int n, m;
vector<vi> adj;
vi istate;

variant<bool, vi> find_journey(int N, int M, vi U, vi V) {
  n = N; m = M; istate.assign(n, 0); adj.resize(n);
  for (int i = 0; i < M; i++) {
    adj[U[i]].push_back(i);
    adj[V[i]].push_back(i);
  }

  queue<state> q;
  q.push(state{1, 0, -1, vector<int>(1, 0), vector<int>(m, 0)});

  int lim = 5*M, step = 0;
  while (!q.empty() && step++ < lim) {
    auto st = q.front(); q.pop();
    if (st.cur == 0 && st.moves > 1 && *max_element(st.config.begin(), st.config.end()) == 0) {
      return st.steps;
    }

    for (auto v : adj[st.cur]) {
      if (v != st.lst && ((U[v] == st.cur && st.config[v] == 0) || (V[v] == st.cur && st.config[v] == 1))) {
        auto ns = state{st.moves, st.cur, st.lst, st.steps, st.config};
        ns.moves++; ns.cur = (U[v] == st.cur ? V[v] : U[v]);
        ns.config[v] = 1-ns.config[v]; ns.steps.push_back(ns.cur); ns.lst = v;
        q.push(ns);
      }
    }
  }
  return false;
}

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