제출 #1320084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320084		madamadam3	수천개의 섬 (IOI22_islands)	C++20	5 / 100	1141 ms	1298688 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);
  map<pair<int, int>, int> pq;
  for (int i = 0; i < m; i++) {
    if (pq[{U[i], V[i]}] >= 2) continue;
    pq[{U[i], V[i]}]++;

    adj[U[i]].push_back(i);
    adj[V[i]].push_back(i);
  }

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

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

    // for (auto &el : st.steps) cout << el << " "; cout << "\n";
    for (auto v : adj[st.cur]) {
      // cout << v << "\n";
      if (v != st.lst && ((U[v] == st.cur) == (st.config[v] == 0))) {
        auto ns = state{st.moves, st.cur, st.lst, vector<int>(), vector<int>()};
        for (auto &el : st.steps) ns.steps.push_back(el);
        for (auto &el : st.config) ns.config.push_back(el);

        ns.moves++; ns.cur = (U[v] == st.cur ? V[v] : U[v]);
        ns.config[v] = 1-ns.config[v]; ns.steps.push_back(v); ns.lst = v;
        q.push(ns);
      }
    }
  }
  return false;
}

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