제출 #787680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787680		thimote75	수천개의 섬 (IOI22_islands)	C++17	35 / 100	170 ms	44248 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);
  idata cycle1 = get_cycle(typed_result[1], b0, b1, U, V);

  idata path0 = get_path(typed_result[0], 0,  b0, U, V);
  idata path1 = get_path(typed_result[1], b0, b1, U, V);

  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) {
    idata answer;

    

    return answer;
  }*/

  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;
}

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, idata, idata)':
islands.cpp:99:8: warning: unused variable 'st3' [-Wunused-variable]
   99 |   bool st3 = M % 2 == 0;
      |        ^~~
islands.cpp:127:8: warning: variable 'intersects' set but not used [-Wunused-but-set-variable]
  127 |   bool intersects = false;
      |        ^~~~~~~~~~

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 15.749999999999998 / 45