Submission #1234866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234866		trimkus	Thousands Islands (IOI22_islands)	C++20	0 / 100	1095 ms	544 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>
using namespace std;

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    vector<vector<array<int, 2>>> adj(N);
    vector<int> deg(N);
    for (int i = 0; i < M; ++i) {
      adj[U[i]].push_back({V[i], i});
    }
    vector<int> path;
    vector<bool> vis(N);
    int cycle_node = -1;
    bool done = false;
    vector<pair<int, int>> with_nodes;
    auto dfs = [&](auto& dfs, int i, int lst) -> bool {
        if (vis[i]) {
          vector<pair<int, int>> to_cycle;
          vector<int> rev;
          while (with_nodes.back().second != i) {
            to_cycle.push_back(with_nodes.back());
            rev.push_back(with_nodes.back().first);
            with_nodes.pop_back();
          }
          to_cycle.push_back(with_nodes.back());
          rev.push_back(with_nodes.back().first);
          with_nodes.pop_back();
          reverse(begin(to_cycle), end(to_cycle));

          // cout << "Found a cycle at " << i << ": ";
          // for (auto& u : rev) {
          //   cout << u << " ";
          // } 
          // cout << "\n";
          int j = i;
          int ptr = 0;
          vector<int> nw;
          do {
            for (auto& [u, id] : adj[j]) {
              // cout << to_cycle[ptr].first << " " << to_cycle[ptr].second << " , " << id << " " << u << "\n";

              if (to_cycle[(ptr + 1) % (int)to_cycle.size()].second != u) continue;
              if (to_cycle[ptr].first == id) continue;;
              nw.push_back(id);
              ptr += 1;
              j = u;
              break;
            }
          } while (j != i);
          auto rev1 = nw;
          reverse(begin(rev1), end(rev1));
          path.insert(end(path), begin(nw), end(nw));
          path.insert(end(path), begin(rev), end(rev));
          path.insert(end(path), begin(rev1), end(rev1));
          set<int> cycle;
          for (auto& u : rev) cycle.insert(u);
          for (auto& u : rev1) cycle.insert(u);
          vector<int> rev2;
          for (auto& u : path) {
            if (cycle.count(u)) break;
            rev2.push_back(u);
          }
          reverse(begin(rev2), end(rev2));
          path.insert(end(path), begin(rev2), end(rev2));
          // cout << "Appended cycle:\n";
          // for (auto& u : path) {
          //   cout << u << " ";
          // }
          // cout << "\n";
          return true;
        }
        vis[i] = 1;
        for (auto& [u, id] : adj[i]) {
          path.push_back(id);
          with_nodes.push_back({id, i});
          if (dfs(dfs, u, i)) {
            return true;
          }
          path.pop_back();
          with_nodes.pop_back();
        }
        vis[i] = 0;
        return false;
    };
    if (dfs(dfs, 0, -1)) return path;
    return false;
}

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