제출 #628114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628114		Turkhuu	수천개의 섬 (IOI22_islands)	C++17	22.75 / 100	30 ms	5284 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
  vector<vector<pair<int, int>>> G(N);
  for (int i = 0; i < M; i++) {
    G[U[i]].emplace_back(V[i], i);
  }
  vector<int> B(N, -1), ans;
  function<bool(int)> dfs = [&](int A) {
    if (A == 0) {
      if (G[0].size() > 1) {
        int X = G[0][0].second;
        int Y = X ^ 1;
        int Z = G[0][1].second;
        int T = Z ^ 1;
        ans = vector<int>({X, Y, Z, T, Y, X, T, Z});
        return true;
      } else if (G[0].size() == 1) {
        auto [E, F] = G[0][0];
        B[E] = F;
        if (dfs(E)) {
          return true;
        }
      }
    } else {
      if (G[A].size() > 2) {
        vector<int> a;
        int C = A;
        while (C != 0) {
          a.push_back(B[C]);
          C = U[B[C]];
        }
        int X = (B[A] == (G[A][0].second ^ 1)) ? G[A][1].second : G[A][0].second;
        int Y = X ^ 1;
        int Z = (B[A] == (G[A][2].second ^ 1)) ? G[A][1].second : G[A][2].second;
        int T = Z ^ 1;
        for (int i = a.size() - 1; i >= 0; i--) {
          ans.push_back(a[i]);
        }
        for (int C : vector<int>({X, Y, Z, T, Y, X, T, Z})) {
          ans.push_back(C);
        }
        for (int i = 0; i < a.size(); i++) {
          ans.push_back(a[i]);
        }
        return true;
      } else if (G[A].size() == 2) {
        pair<int, int> P;
        if (B[A] == (G[A][0].second ^ 1)) {
          P = G[A][1];
        } else {
          P = G[A][0];
        }
        auto [E, F] = P;
        if (B[E] == -1) {
          B[E] = F;
          if (dfs(E)) {
            return true;
          }
        }
      }
    }
    return false;
  };
  B[0] = -2;
  if (dfs(0)) {
    return ans;
  } else {
    return false;
  }
}

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

islands.cpp: In lambda function:
islands.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~

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