Submission #825780

#	Time	Username	Problem	Language	Result	Execution time	Memory
825780		top34051	Thousands Islands (IOI22_islands)	C++17	0 / 100	4 ms	5096 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>

const int maxn = 1e5 + 5;

std::vector<std::pair<int, std::pair<int, int>>> way[maxn];
std::vector<int> path, ans;
int goal;
bool subtask3_completed, vis[maxn];

void subtask3(int u, int last) {
  vis[u] = true;
  if (u == goal) {
    std::vector<int> has;
    for (auto &[v, idx] : way[u]) {
      int i = idx.first, j = idx.second;
      if (i == last || j == last) continue;
      has.push_back(i);
      has.push_back(j);
      if ((int)has.size() == 4) break;
    }
    ans = path;
    ans.push_back(has[0]);
    ans.push_back(has[1]);
    ans.push_back(has[2]);
    ans.push_back(has[3]);
    ans.push_back(has[1]);
    ans.push_back(has[0]);
    ans.push_back(has[3]);
    ans.push_back(has[2]);
    for (int i = (int)path.size() - 1; i >= 0; --i) {
      ans.push_back(path[i]);
    }
    subtask3_completed = true;
  }
  for (auto &[v, idx] : way[u]) {
    int i = idx.first;
    if (vis[v]) continue;
    path.push_back(i);
    subtask3(v, i);
    path.pop_back();
  }
}

std::variant<bool, std::vector<int>> find_journey(int N, int M,
                                                  std::vector<int> U,
                                                  std::vector<int> V) {
  // Subtask 1
  if (N == 2) {
    std::vector<int> a, b;
    for (int i = 0; i < M; ++i) {
      int u = U[i];
      if (u == 0) {
        a.push_back(i);
      } else {
        b.push_back(i);
      }
    }
    if ((int)a.size() >= 2 && (int)b.size() >= 1) {
      return std::vector({a[0], b[0], a[1], a[0], b[0], a[1]});
    }
  }
  // Subtask 2
  if (N >= 2) {
    std::vector<std::vector<int>> id(3, std::vector<int>(3, -1));
    for (int i = 0; i < M; ++i) {
      int u = U[i], v = V[i];
      if (u * v == 0 && u <= 2 && v <= 2) {
        id[u][v] = i;
      }
    }
    if (id[0][1] != -1 && id[1][0] != -1 && id[0][2] != -1 && id[2][0] != -1) {
      return std::vector({id[0][1], id[1][0], id[0][2], id[2][0], id[1][0],
                          id[0][1], id[2][0], id[0][2]});
    }
  }
  // Subtask 3
  for (int i = 0; i < M; ++i) {
    if (i % 2 == 0) {
      way[U[i]].push_back({V[i], {i, i + 1}});
    } else {
      way[U[i]].push_back({V[i], {i, i - 1}});
    }
  }
  for (int u = 0; u < N; ++u) {
    if ((int)way[u].size() >= 3 - (u == 0)) goal = u;
  }
  subtask3(0, 0);
  if (subtask3_completed) return ans;
  return false;
}

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