Submission #627262

#	Time	Username	Problem	Language	Result	Execution time	Memory
627262		model_code	Thousands Islands (IOI22_islands)	C++17	26 / 100	1105 ms	745980 KiB

islands

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

#include <bits/stdc++.h>

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

std::variant<bool, std::vector<int>> find_journey(int, int M, std::vector<int> U, std::vector<int> V) {
  // adj vector
  std::vector<edge> path[1111], path_rev[1111];
  for (int i = 0; i < M; i++){
    path[U[i]].push_back({V[i], i});
    path_rev[V[i]].push_back({U[i], i});
  }

  // move forward until we find a node with > 1 new outdegree (not including the one we come from)
  int curr_pos = 0;
  int prev = -1;
  std::vector<int> sol, tmp;

  while (true) {
    if (curr_pos == 0 && path[curr_pos].size() == 0) // dead-end
      return false;
    else if (curr_pos != 0 && path[curr_pos].size() == 1) // dead-end
      return false;
    // we're at the 0, and and only have 1 path forward
    else if (curr_pos == 0 && path[curr_pos].size() == 1) {
      int idx = 0;

      prev = curr_pos;
      tmp.push_back(path[curr_pos][idx].second);
      curr_pos = path[curr_pos][idx].first;
    }
    // we're somewhere in the middle, and only have 1 new path forward
    else if (curr_pos != 0 && path[curr_pos].size() == 2) {
      int idx = 0;
      // make sure we're not going back again
      if (path[curr_pos][idx].first == prev) idx = 1;

      prev = curr_pos;
      tmp.push_back(path[curr_pos][idx].second);
      curr_pos = path[curr_pos][idx].first;

    }
    else {
      // branch found.
      // to to left, then right, then do that again.
      int Lidx, Ridx;

      // find the left and the right onen.
      if (path[curr_pos][0].first == prev) {
        Lidx = 1;
        Ridx = 2;
      } else if (path[curr_pos][1].first == prev) {
        Lidx = 0;
        Ridx = 2;
      } else {
        Lidx = 0;
        Ridx = 1;
      }
      int L = path[curr_pos][Lidx].second;
      int R = path[curr_pos][Ridx].second;

      int toL = path[curr_pos][Lidx].first;
      int toR = path[curr_pos][Ridx].first;
      
      // find an edge back
      int Lrev, Rrev;
      for (auto e: path[toL]) {
        if (e.first == curr_pos) Lrev = e.second;
      }
      for (auto e: path[toR]) {
        if (e.first == curr_pos && e.second != Lrev) Rrev = e.second;
      }

      // <path from 0 to X> - L - Lrev - R - Rrev - Lrev - L Rrev - R - <back to 0>
      int TS = tmp.size();
      for (int i = 0; i < TS; i++)
        sol.push_back(tmp[i]);

      sol.push_back(L);
      sol.push_back(Lrev);
      sol.push_back(R);
      sol.push_back(Rrev);

      sol.push_back(Lrev);
      sol.push_back(L);
      sol.push_back(Rrev);
      sol.push_back(R);
      
      for (int i = TS - 1; i >= 0; i--)
        sol.push_back(tmp[i]);

      return sol;
    }

  }
  return false;
}

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