Submission #627257

#	Time	Username	Problem	Language	Result	Execution time	Memory
627257		model_code	Thousands Islands (IOI22_islands)	C++17	100 / 100	360 ms	47916 KiB

islands

// model_solution/solution.cpp
#include "islands.h"

#include <bits/stdc++.h>

#define edge std::pair<int,int>


int mode[111000];

std::vector<std::set<edge>> back_path(222000);
std::vector<std::set<edge>> path(222000);
std::queue<int> remove_q;

bool must_flip = false;

int path_1_loop, path_2_loop;


void put_path(std::vector<int> &sol, std::vector<int> &mirror_sol, std::vector<std::pair<int, int>> &path_1, int loop_id) {
  bool start = false;
  for (int i = 1; i < (int) path_1.size(); i++) {
      int u = path_1[i - 1].first;
      int v = path_1[i].first;

      if ((!start && u == loop_id) || (start && v == loop_id)) {
        start = 1;
        mirror_sol.push_back(1);
      }
      else
        mirror_sol.push_back(0);

      if (path_1[i].second == 1)
        sol.push_back(path[u].begin()->first);
      else
        sol.push_back(path[v].begin()->first);  
    }
}

// remove a node X
void remove_node(int X) {
  // remove node 'curr', and all paths from/to them
    for (auto e: back_path[X]) {
      auto e_id = e.first;
      auto v = e.second;
      path[v].erase({e_id, X});
      if ((int) path[v].size() == 0) remove_q.push(v);
    }

    for (auto e: path[X]) {
      auto e_id = e.first;
      auto v = e.second;
      back_path[v].erase({e_id, X});
    } 
}

// chain-remove all 0 outdegrees
void clear_unused_nodes() {
  while (remove_q.size()) {
    int curr = remove_q.front();
    remove_q.pop();

    remove_node(curr);  
  }
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
  // construct the graph
  for (int i = 0; i < M; i++) {
    path[U[i]].insert({i, V[i]});
    back_path[V[i]].insert({i, U[i]});
  }

  for (int i = 0; i < N; i++)
    if ((int) path[i].size() == 0) remove_q.push(i);
  
  int START = 0;
  std::vector<int> backtrack;
  std::vector<int> init_sol;
  std::vector<int> back_sol;

  while (true) {
    clear_unused_nodes();
    // if START is removed, then no solution
    if ((int) path[START].size() == 0) return false;

    // if START outdeg is 1, move forward and start from there.



    if ((int) path[START].size() == 1) {
      backtrack.push_back(START);
      auto prev_start = START;
      init_sol.push_back(path[START].begin()->first);
      back_sol.push_back(path[START].begin()->first);

      START = path[START].begin()->second;
      
      remove_node(prev_start);
      continue;
    }

 
    // now, we start at START, which has >= 2 outdeg.
    // find a solution.

    // step 1: find a loop
    bool seen[111000];
    memset(seen, 0, sizeof(seen));

    // path notation: second denotes direction
    std::vector<std::pair<int, int>> path_1;
    std::vector<int> first_loop;


    int curr = START;

    while (true) {
      path_1.push_back({curr, 1});
      mode[curr] = 1;
      // loop found
      if (seen[curr]) {
        path_1_loop = curr;
        int X = path_1.size();
        
        bool reverse_mode = false;
        for (int i = X - 1; i >= 0; i--) {
          if (reverse_mode) {
            path_1.push_back({path_1[i].first, 0});
          }
          else {
            // the loop
            first_loop.push_back(path_1[i].first);
            mode[path_1[i].first] = 2;
          }
          if (i != X - 1 && path_1[i].first == curr) reverse_mode = true;
        }

        break;
      } 

      seen[curr] = 1;
      int next = path[curr].begin()->second;  /// guaranteed exists
      curr = next;
    }

    // step 2: find another loop
    // path notation: second denotes direction
    std::vector<std::pair<int, int>> path_2;

    curr = path[START].rbegin()->second;

    while (true) {

      path_2_loop = curr;
      path_2.push_back({curr, 1});
      if (seen[curr]) {
        // 3 cases:
        // 1st cases, found a straight path from path_1.
        if (mode[curr] == 1) {
          int curr2 = path[curr].begin()->second;

          while (mode[curr2] == 1) {
            path_2.push_back({curr2, 1});
            curr2 = path[curr2].begin()->second;
          }
          //backloop
          path_2.push_back({first_loop[0], 1});
          for (int i = 1; i < (int) first_loop.size(); i++) {
            path_2.push_back({first_loop[i], 0});
          }
          // set for trackback
          curr = first_loop[0];
        }

        else if (mode[curr] == 2) {
          // go back reverse circle
          // find the starting point
          int st = 0;
          for (int i = 0; i < (int) first_loop.size(); i++) {
            if (first_loop[i] == curr) {
              st = i + 1;
              break;
            }
          }

          // from st to end
          for (int i = st; i < (int) first_loop.size(); i++) {
            path_2.push_back({first_loop[i], 0});
          }
          // from begin to st
          for (int i = 1; i < st; i++) {
              path_2.push_back({first_loop[i], 0});
          }
        } else if (mode[curr] == 3) {
          must_flip = true;
        }

        int X = path_2.size();
        
        bool reverse_mode = false;
        for (int i = X - 1; i >= 0; i--) {
          if (reverse_mode) {
            path_2.push_back({path_2[i].first, 0});
          }
          if (i != X - 1 && path_2[i].first == curr) reverse_mode = true;
        }
        break;
      }
      mode[curr] = 3;
      seen[curr] = 1;
      curr = path[curr].begin()->second;
    }

    // has a solution
    // convert paths to edges
    std::vector<int> sol;
    std::vector<int> mirror_sol;


    put_path(sol, mirror_sol, path_1, path_1_loop);
    mirror_sol.push_back(0);
    sol.push_back(path[START].rbegin()->first);

    put_path(sol, mirror_sol, path_2, path_2_loop);
    
    mirror_sol.push_back(0);
    sol.push_back(path[START].rbegin()->first);

    
    if (must_flip) {
      int X = sol.size();
      std::stack<int> stack_path;
      bool stack_fill_mode = 0;

      for (int i = 0; i < X; i++) {
        while (!stack_fill_mode && stack_path.size()) {
          int tmp = stack_path.top();
          stack_path.pop();
          sol.push_back(tmp);
        }
        if (mirror_sol[i] == 1) {
          stack_fill_mode ^= 1;
        }

        if (stack_fill_mode)
          stack_path.push(sol[i]);
        else
          sol.push_back(sol[i]);
      }
    }


    for (auto x: sol){
      init_sol.push_back(x);
    }

    std::reverse(back_sol.begin(), back_sol.end());
    for (auto x: back_sol){
      init_sol.push_back(x);
    }

    return init_sol;
  }
}

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