Submission #627264

#	Time	Username	Problem	Language	Result	Execution time	Memory
627264		model_code	Thousands Islands (IOI22_islands)	C++17	24 / 100	65 ms	13012 KiB

islands

// failed/solution-double.cpp
#include "islands.h"

#include <bits/stdc++.h>

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

int ret_paths[111000];
bool in_path[1111];
bool visited[1111];

// we use adj matrix
int path[1111][1111];
int dbl_path[1111][1111];

int path_len;

int dfs(int pos, int N, int id) {
  // std::cout<<"jalan " << pos << std::endl;
  if (visited[pos]) {
    if (in_path[pos]) {
      ret_paths[id] = pos;
      path_len = id;
      return pos;
    }
    else
      return -1;
  }
  
  ret_paths[id] = pos;

  visited[pos] = 1;
  in_path[pos] = 1;

  for (int i = 0; i < N; i++) {
    if (path[pos][i] != -1) {
      int ret = dfs(i, N, id + 1);
      if (ret != -1)
        return ret;
    }
  }

  // std::cout<<"backtrack " << pos << std::endl;
  in_path[pos] = 0;
  return -1;
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
  // construct the graph

  memset(path, -1, sizeof(path));
  memset(dbl_path, -1, sizeof(dbl_path));
  memset(visited, 0, sizeof(visited));
  memset(in_path, 0, sizeof(in_path));


  for (int i = 0; i < M; i++) {
    int u = U[i];
    int v = V[i];

    if (path[u][v] == -1) path[u][v] = i;
    else dbl_path[u][v] = i;
  }

  // find a circle
  int circle_start = dfs(0, N, 0);
  // std::cout<< "CIRCLE " << circle_start << std::endl;

  if (circle_start == -1) return false;

  // buildpath
  std::vector<int> sol;
  int circle_id = -1;
  for (int i = 0; i < path_len; i++) {
    if (ret_paths[i] == circle_start) {
      circle_id = i;
      break;
    }
  }
  // 0 -> 1 -> ... -> circle -> ... -> circle
  for (int i = 0; i < path_len; i++)
    sol.push_back(path[ret_paths[i]][ret_paths[i + 1]]);

  // 2nd loop
  // circle -> ... -> circle
  for (int i = circle_id; i < path_len; i++)
    sol.push_back(dbl_path[ret_paths[i]][ret_paths[i + 1]]);

  // inverse circle 1st
  for (int i = path_len; i > circle_id; i--)
    sol.push_back(path[ret_paths[i - 1]][ret_paths[i]]);

  // inverse circle 2nd
  for (int i = path_len; i > circle_id; i--)
    sol.push_back(dbl_path[ret_paths[i - 1]][ret_paths[i]]);

  // go home
  for (int i = circle_id; i > 0; i--)
    sol.push_back(path[ret_paths[i - 1]][ret_paths[i]]);

  return sol;
}

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