Submission #1234799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234799		trimkus	Thousands Islands (IOI22_islands)	C++20	26 / 100	16 ms	4680 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;
    auto dfs = [&](auto& dfs, int i, int lst) -> bool {
        int cnt = 0;
        for (auto& [u, id] : adj[i]) {
          if (u == lst) continue;
          cnt += 1;
        }
        if (cnt >= 2) {
            auto rev = path;
            reverse(begin(rev), end(rev));
            int c1 = -1, c2 = -1;
            int u1 = -1, u2 = -1;
            for (auto& [u, id] : adj[i]) {
                if (u == lst) continue;
                if (c1 == -1 || c2 == -1) {
                  if (u1 == -1) u1 = u;
                  else if (u1 != u) u2 = u;
                  if (c1 == -1) c1 = id;
                  else c2 = id;
                }
            }
            assert(u1 != -1);
            assert(c1 != -1);
            assert(c2 != -1);
            int c3 = -1, c4 = -1;
            for (auto& [u, id] : adj[u1]) {
                if (u == i) {
                    c3 = id;
                    break;
                }
            }
            if (u2 != -1) {
              for (auto& [u, id] : adj[u2]) {
                if (u == i) {
                  c4 = id;
                  break;
                }
              }
            }
            assert(c3 != -1);
            if (c4 == -1) {
              path.push_back(c1);
              path.push_back(c3);
              path.push_back(c2);
              path.push_back(c1);
              path.push_back(c3);
              path.push_back(c2);
            } else {
              path.push_back(c1);
              path.push_back(c3);
              path.push_back(c2);
              path.push_back(c4);
              path.push_back(c3);
              path.push_back(c1);
              path.push_back(c4);
              path.push_back(c2);
            }
            path.insert(path.end(), begin(rev), end(rev));
            return true;
        }
        for (auto& [u, id] : adj[i]) {
          if (u == lst) continue;
          path.push_back(id);
          if (dfs(dfs, u, i)) {
            return true;
          }
          path.pop_back();
        }
        return false;
    };
    if (dfs(dfs, 0, -1)) return path;
    return false;
}

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