Submission #627258

#	Time	Username	Problem	Language	Result	Execution time	Memory
627258		model_code	Thousands Islands (IOI22_islands)	C++17	100 / 100	425 ms	44136 KiB

islands

// correct/solution-ayaze-full.cpp
#include "islands.h"

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

vector<set<pair<int, int>>> adj_list, rev_adj_list;
queue<int> unprocessed_zero_outdeg;

void RemoveNode(int v) {
  for (auto [u, edge_idx] : adj_list[v]) {
    rev_adj_list[u].erase({v, edge_idx});
  }

  for (auto [u, edge_idx] : rev_adj_list[v]) {
    adj_list[u].erase({v, edge_idx});

    if (adj_list[u].empty()) {
      unprocessed_zero_outdeg.push(u);
    }
  }

  adj_list[v].clear();
  rev_adj_list[v].clear();
}

// nodes, edge idxs
// last node is the first cyclic node
pair<vector<int>, vector<int>> FindCycle(int u, bool take_second) {
  auto it = adj_list[u].begin();
  if (take_second) ++it;

  set<int> seen = {u};
  vector<int> nodes = {u};
  vector<int> edge_idxs = {};

  auto [v, edge_idx] = *it;
  while (!seen.count(v)) {
    nodes.push_back(v);
    edge_idxs.push_back(edge_idx);
    seen.insert(v);

    edge_idx = adj_list[v].begin()->second;
    v = adj_list[v].begin()->first;
  }

  nodes.push_back(v);
  edge_idxs.push_back(edge_idx);
  return {nodes, edge_idxs};
}

pair<vector<int>, vector<int>> ConstructSimpleCycle(vector<int> nodes, vector<int> edge_idxs) {
  int first_occ = -1;
  for (int i = 0 ; i+1 < static_cast<int>(nodes.size()) ; i++) {
    if (nodes[i] == nodes.back()) {
      first_occ = i;
      break;
    }
  }

  vector<int> first_path;
  for (int i = 0 ; i < static_cast<int>(edge_idxs.size()) ; i++) {
    first_path.push_back(edge_idxs[i]);
  }
  for (int i = first_occ-1 ; i >= 0 ; i--) {
    first_path.push_back(edge_idxs[i]);
  }

  vector<int> second_path;
  for (int i = 0 ; i < first_occ ; i++) {
    second_path.push_back(edge_idxs[i]);
  }
  for (int i = static_cast<int>(edge_idxs.size())-1 ; i >= 0 ; i--) {
    second_path.push_back(edge_idxs[i]);
  }

  return {first_path, second_path};
}

void FindTour(int u, vector<int> &ans) {
  while (!unprocessed_zero_outdeg.empty()) {
    int v = unprocessed_zero_outdeg.front();
    unprocessed_zero_outdeg.pop();
    RemoveNode(v);
  }

  if (adj_list[u].empty()) {
    ans.push_back(-1);
    return;
  }

  if (static_cast<int>(adj_list[u].size()) == 1) {
    auto [v, edge_idx] = *adj_list[u].begin();
    ans.push_back(edge_idx);
    RemoveNode(u);
    FindTour(v, ans);
    ans.push_back(edge_idx);
    return;
  }

  auto [first_cycle, first_cycle_edges] = FindCycle(u, false);
  auto [second_cycle, second_cycle_edges] = FindCycle(u, true);

  map<int, int> first_occ;
  for (int i = 0 ; i+1 < static_cast<int>(first_cycle.size()) ; i++) {
    first_occ[first_cycle[i]] = i;
  }
  int common_node = -1;
  int first_common_occ = -1;
  int second_common_occ = -1;
  for (int i = 1 ; i+1 < static_cast<int>(second_cycle.size()) ; i++) {
    if (first_occ.count(second_cycle[i])) {
      common_node = second_cycle[i];
      second_common_occ = i;
      first_common_occ = first_occ[common_node];
      break;
    }
  }

  if (common_node == -1) { // two disjoint cycles
    auto cycle1 = ConstructSimpleCycle(first_cycle, first_cycle_edges);
    auto cycle2 = ConstructSimpleCycle(second_cycle, second_cycle_edges);

    ans.insert(ans.end(), cycle1.first.begin(), cycle1.first.end());
    ans.insert(ans.end(), cycle2.first.begin(), cycle2.first.end());
    ans.insert(ans.end(), cycle1.second.begin(), cycle1.second.end());
    ans.insert(ans.end(), cycle2.second.begin(), cycle2.second.end());
    return;
  }

  int first_cyclic_occ = -1;
  for (int i = 0 ; i+1 < static_cast<int>(first_cycle.size()) ; i++) {
    if (first_cycle[i] == first_cycle.back()) {
      first_cyclic_occ = i;
      break;
    }
  }
  
  // loop the first path
  for (int i = 0 ; i < static_cast<int>(first_cycle_edges.size()) ; i++) {
    ans.push_back(first_cycle_edges[i]);
  }
  for (int i = first_cyclic_occ-1 ; i >= 0 ; i--) {
    ans.push_back(first_cycle_edges[i]);
  }

  // enter first path through second path
  for (int i = 0 ; i < second_common_occ ; i++) {
    ans.push_back(second_cycle_edges[i]);
  }

  // only one of the following loops will be executed; we want
  // to reach the start of the cycle
  for (int i = first_common_occ-1 ; i >= first_cyclic_occ ; i--) {
    ans.push_back(first_cycle_edges[i]);
  }
  for (int i = first_common_occ ; i < first_cyclic_occ ; i++) {
    ans.push_back(first_cycle_edges[i]);
  }

  // go back through the latter part of first path and second path
  for (int i = static_cast<int>(first_cycle_edges.size())-1 ; i >= first_common_occ ; i--) {
    ans.push_back(first_cycle_edges[i]);
  }
  for (int i = second_common_occ-1 ; i >= 0 ; i--) {
    ans.push_back(second_cycle_edges[i]);
  }
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
  
  adj_list.resize(N);
  rev_adj_list.resize(N);
  for (int i = 0 ; i < M ; i++) {
    adj_list[U[i]].insert({V[i], i});
    rev_adj_list[V[i]].insert({U[i], i});
  }
  for (int i = 0 ; i < N ; i++) {
    if (adj_list[i].empty()) {
      unprocessed_zero_outdeg.push(i);
    }
  }

  vector<int> ret;
  FindTour(0, ret);

  for (int e : ret) {
    if (e == -1) {
      return false;
    }
  }

  return ret;
}

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