제출 #1198627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198627		abczz	Thousands Islands (IOI22_islands)	C++20	14.10 / 100	41 ms	15544 KiB

islands

#include "islands.h"
#include <iostream>
#include <variant>
#include <vector>
#include <map>
#define ll long long

using namespace std;

bool visited[100000];
bool B[100000], done[100000];
map <ll, ll> mp;
ll id[100000];
vector <array<ll, 2> > adj[100000];
vector <ll> X, C, F, G;
vector <int> ans;
ll k;

ll search(ll u) {
  ++mp[u];
  visited[u] = k;
  while (id[u] < adj[u].size()) {
    ll v = adj[u][id[u]++][0];
    if (done[v]) continue;
    G.push_back(adj[u][id[u]-1][1]);
    if (B[v]) return 1;
    else if (visited[v] == k) {
      return 2;
    }
    else if (!visited[v]) {
      ll res = search(v);
      if (res) return res;
    }
    G.pop_back();
  }
  return 0;
}
ll dfs(ll u) {
  ++mp[u];
  visited[u] = 1;
  while (id[u] < adj[u].size()) {
    ll v = adj[u][id[u]++][0];
    if (done[v]) continue;
    F.push_back(adj[u][id[u]-1][1]);
    if (visited[v] == 1) {
      C.push_back(u);
      B[u] = 1;
      return v;
    }
    else if (visited[v] == 0) {
      ll ret = dfs(v);
      if (ret == -2) {
        B[u] = 1;
        X.push_back(u);
        return -2;
      }
      else if (ret != -1) {
        B[u] = 1;
        if (ret != u) {
          C.push_back(u);
          return ret;
        }
        else {
          X.push_back(u);
          return -2;
        }
      }
    }
    F.pop_back();
  }
  return -1;
}
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
  X.clear();
  C.clear();
  F.clear();
  G.clear();
  mp.clear();
  ans.clear();
  k = 2;
  for (int i=0; i<N; ++i) visited[i] = B[i] = done[i] = id[i] = 0;
  for (int i=0; i<M; ++i) {
    adj[U[i]].push_back({V[i], i});
  }
  ll nx = 0;
  while (dfs(nx) == -2) {
    while (!X.empty()) {
      auto u = X.back();
      X.pop_back();
      ll res = search(u);
      if (res) {
        for (auto v : F) ans.push_back(v);
        bool ok = 0;
        vector <int> tmp, cyc;
        for (auto v : F) {
          if (U[v] == V[F.back()]) ok = 1;
          if (ok) cyc.push_back(v);
        }
        ok = 0;
        for (auto v : F) {
          if (U[v] == u) ok = 1;
          if (U[v] == V[F.back()]) ok = 0;
          if (ok) tmp.push_back(v);
        }
        for (int i = (ll)tmp.size()-1; i>=0; --i) {
          ans.push_back(tmp[i]);
        }
        for (auto v : G) ans.push_back(v);
        if (res == 1) {
          ok = 0;
          ll start = -1;
          for (auto v : F) {
            if (U[v] == V[G.back()]) ok = 1;
            if (U[v] == V[F.back()]) {
              if (ok) start = U[v];
              break;
            }
            if (ok) ans.push_back(v);
          }
          if (start == -1) start = V[G.back()];
          ok = 0;
          for (int i=cyc.size()-1; i>=0; --i) {
            if (V[cyc[i]] == start) ok = 1;
            if (ok) ans.push_back(cyc[i]);
          }
          if (start != U[cyc[0]]) {
            for (int i=cyc.size()-1; i>=0; --i) {
              ans.push_back(cyc[i]);
              if (U[cyc[i]] == start) break;
            }
          }
          ok = 0;
          for (int i=F.size()-2; i>=0; --i) {
            if (V[F[i]] == V[F.back()]) ok = 1;
            if (ok) ans.push_back(F[i]);
            if (U[F[i]] == V[G.back()]) break;
          }
          for (int i=G.size()-1; i>=0; --i) ans.push_back(G[i]);
          return ans;
          ok = 0;
          for (int i=F.size()-2; i>=0; --i) {
            if (V[F[i]] == u) ok = 1;
            if (ok) ans.push_back(F[i]);
          }
        }
        else {
          ok = 0;
          for (int i=G.size()-2; i>=0; --i) {
            if (V[G[i]] == V[G.back()]) ok = 1;
            if (ok) ans.push_back(G[i]);
          }
          ok = 0;
          for (auto v : F) {
            if (U[v] == u) ok = 1;
            if (U[v] == V[F.back()]) break;
            if (ok) ans.push_back(v);
          }
          for (int i=F.size()-1; i>=0; --i) {
            ans.push_back(F[i]);
            if (U[F[i]] == u) break;
          }
          for (auto v : G) {
            if (U[v] == V[G.back()]) break;
            ans.push_back(v);
          }
          for (int i=G.size()-1; i>=0; --i) {
            ans.push_back(G[i]);
            if (U[G[i]] == u) break;
          }
          ok = 0;
          for (int i=F.size()-2; i>=0; --i) {
            if (V[F[i]] == u) ok = 1;
            if (ok) ans.push_back(F[i]);
          }
        }
        return ans;
      }
      B[u] = 0;
      ++k;
    }
    for (auto u : C) {
      B[u] = 0;
      --id[u];
      mp.erase(u);
    }
    for (auto [x, y] : mp) {
      done[x] = 1;
    }
    mp.clear();
    nx = C.back();
    C.clear();
    G.clear();
    while (!F.empty()) {
      auto u = F.back();
      if (V[u] != nx) F.pop_back();
      else break;
    }
  }
  return false;
}

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