Submission #787670

#	Time	Username	Problem	Language	Result	Execution time	Memory
787670		thimote75	Thousands Islands (IOI22_islands)	C++17	0 / 100	2 ms	596 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
using graph = vector<vector<pair<pair<int, bool>, int>>>;
using bdata = vector<bool>;
using bgrid = vector<bdata>;

graph roads;

bgrid visited;
bgrid visiting;
bdata used;
idata path;

idata result;
igrid typed_result;

int b0 = -1;
int b1 = -1;

bool dfs (int node, int type, int last) {
  if (visited[node][type] && !visiting[node][type]) return false;
  
  if (visiting[node][type]) {
    if (type == 1) { b1 = node; return true; }
    b0 = node;

    type ++;
    if (visited[node][type]) return false;
  }

  visiting[node][type] = true;
  visited [node][type] = true;

  for (const auto &road : roads[node]) {
    int id   = road.first.first;
    int next = road.second;
    if (used[id] != road.first.second || last == id) continue ;

    used[id] = !road.first.second;
    result.push_back(id);
    typed_result[type].push_back(id);
    if (dfs(next, type, id))
      return true;
    typed_result[type].pop_back();
    result.pop_back();
    used[id] = road.first.second;
  }

  visiting[node][type] = false;
  return false;
}

idata get_cycle (idata &path, int node, int pivot, idata &U, idata &V) {
  bool f_pivot = node == pivot;

  idata cycle;
  for (int road_id : path) {
    if (f_pivot) cycle.push_back(road_id);

    node = U[road_id] == node ? V[road_id] : U[road_id];
    f_pivot |= node == pivot;
  }

  return cycle;
}
idata get_path (idata &path, int node, int pivot, idata &U, idata &V) {
  bool f_pivot = node != pivot;

  idata cycle;
  for (int road_id : path) {
    if (f_pivot) cycle.push_back(road_id);

    node = U[road_id] == node ? V[road_id] : U[road_id];
    f_pivot &= node != pivot;
  }

  return cycle;
}

void append (idata &answer, idata path, bool reversed) {
  if (reversed)
    reverse(path.begin(), path.end());
  
  for (int u : path) answer.push_back(u);
}

std::variant<bool, idata> find_journey(
    int N, int M, idata U, idata V) {
  roads.resize(N);
  typed_result.resize(2);
  visited.resize(N, bdata(2)); visiting.resize(N, bdata(2));
  used.resize(M);
  bool st3 = M % 2 == 0;
  for (int i = 0; i < M; i ++) {
    roads[U[i]].push_back({ {i, false}, V[i] });
    roads[V[i]].push_back({ {i, true }, U[i] });
  }
  
  if (!dfs(0, 0, -1)) return false;

  idata cycle0 = get_cycle(typed_result[0], 0,  b0, U, V);
  for (int u : cycle0) cout << u << " "; cout << endl;
  idata cycle1 = get_cycle(typed_result[1], b0, b1, U, V);
  for (int u : cycle1) cout << u << " "; cout << endl;

  idata path0 = get_path(typed_result[0], 0,  b0, U, V);
  for (int u : path0) cout << u << " "; cout << endl;
  idata path1 = get_path(typed_result[1], b0, b1, U, V);
  for (int u : path1) cout << u << " "; cout << endl;

  idata count_cycle(M);
  for (int u : cycle0) count_cycle[u] ++;
  for (int u : cycle1) count_cycle[u] ++;
  idata count_path(M);
  for (int u : path0) count_path[u] ++;
  for (int u : path1) count_path[u] ++;

  idata bpath;
  for (int u : path0) if (count_path[u] == 1) bpath.push_back(u);
  idata dpath0;
  for (int u : path0) if (count_path[u] == 2) dpath0.push_back(u);
  idata dpath1;
  for (int u : path1) if (count_path[u] == 1) dpath1.push_back(u);

  bool intersects = false;
  for (int u : count_cycle) if (u == 2) intersects = true;

  if (intersects) return true;

  idata answer;
  append(answer, bpath, false);
  
  append(answer, dpath0, false);
  append(answer, cycle0, false);
  append(answer, dpath0, true);

  append(answer, dpath1, false);
  append(answer, cycle1, false);
  append(answer, dpath1, true);

  append(answer, dpath0, false);
  append(answer, cycle0, true);
  append(answer, dpath0, true);

  append(answer, dpath1, false);
  append(answer, cycle1, true);
  append(answer, dpath1, true);

  append(answer, bpath, true);

  return answer;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, idata, idata)':
islands.cpp:108:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  108 |   for (int u : cycle0) cout << u << " "; cout << endl;
      |   ^~~
islands.cpp:108:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |   for (int u : cycle0) cout << u << " "; cout << endl;
      |                                          ^~~~
islands.cpp:110:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |   for (int u : cycle1) cout << u << " "; cout << endl;
      |   ^~~
islands.cpp:110:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |   for (int u : cycle1) cout << u << " "; cout << endl;
      |                                          ^~~~
islands.cpp:113:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  113 |   for (int u : path0) cout << u << " "; cout << endl;
      |   ^~~
islands.cpp:113:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  113 |   for (int u : path0) cout << u << " "; cout << endl;
      |                                         ^~~~
islands.cpp:115:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  115 |   for (int u : path1) cout << u << " "; cout << endl;
      |   ^~~
islands.cpp:115:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  115 |   for (int u : path1) cout << u << " "; cout << endl;
      |                                         ^~~~
islands.cpp:99:8: warning: unused variable 'st3' [-Wunused-variable]
   99 |   bool st3 = M % 2 == 0;
      |        ^~~

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