提出 #47300664

ソースコード 拡げる

#include <iostream>
#include <vector>
using namespace std;

constexpr int nmax = 200200;
int N, M;
int A[nmax], B[nmax];
vector<int> g[nmax];
int X[nmax];
int bipartite = true;

void dfs(int c, int x) {
  X[c] = x;
  for (auto& d : g[c]) {
    if (X[d] == -1) {
      dfs(d, 1 - x);
    } else if (X[d] == X[c]) {
      bipartite = false;
    }
  }
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) cin >> A[i], A[i]--;
  for (int i = 0; i < M; i++) cin >> B[i], B[i]--;
  for (int i = 0; i < M; i++) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }

  for (int i = 0; i < N; i++) X[i] = -1;
  for (int i = 0; i < N; i++) {
    if (X[i] == -1) dfs(i, 0);
  }
  cout << (bipartite ? "Yes" : "No") << endl;
}

提出情報

提出日時
問題 D - Good Tuple Problem
ユーザ MegaSam
言語 C++ 20 (gcc 12.2)
得点 400
コード長 772 Byte
結果 AC
実行時間 96 ms
メモリ 26120 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 4
AC × 27
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_1_00.txt, 01_random_1_01.txt, 01_random_1_02.txt, 01_random_1_03.txt, 01_random_1_04.txt, 02_random_2_00.txt, 02_random_2_01.txt, 02_random_2_02.txt, 02_random_2_03.txt, 02_random_2_04.txt, 02_random_2_05.txt, 02_random_2_06.txt, 02_random_2_07.txt, 02_random_2_08.txt, 02_random_2_09.txt, 03_tree_00.txt, 04_path_00.txt, 05_corner_00.txt, 05_corner_01.txt, 05_corner_02.txt, 05_corner_03.txt, 05_corner_04.txt, 05_corner_05.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 2 ms 3520 KiB
00_sample_01.txt AC 2 ms 3516 KiB
00_sample_02.txt AC 2 ms 3512 KiB
00_sample_03.txt AC 2 ms 3476 KiB
01_random_1_00.txt AC 12 ms 5864 KiB
01_random_1_01.txt AC 9 ms 7596 KiB
01_random_1_02.txt AC 12 ms 6940 KiB
01_random_1_03.txt AC 14 ms 9432 KiB
01_random_1_04.txt AC 42 ms 8352 KiB
02_random_2_00.txt AC 25 ms 5552 KiB
02_random_2_01.txt AC 33 ms 6552 KiB
02_random_2_02.txt AC 22 ms 5420 KiB
02_random_2_03.txt AC 30 ms 5688 KiB
02_random_2_04.txt AC 28 ms 5584 KiB
02_random_2_05.txt AC 24 ms 5432 KiB
02_random_2_06.txt AC 30 ms 6248 KiB
02_random_2_07.txt AC 41 ms 6768 KiB
02_random_2_08.txt AC 28 ms 6180 KiB
02_random_2_09.txt AC 42 ms 7056 KiB
03_tree_00.txt AC 88 ms 16944 KiB
04_path_00.txt AC 84 ms 26116 KiB
05_corner_00.txt AC 2 ms 3508 KiB
05_corner_01.txt AC 37 ms 6840 KiB
05_corner_02.txt AC 36 ms 6668 KiB
05_corner_03.txt AC 36 ms 6500 KiB
05_corner_04.txt AC 84 ms 26120 KiB
05_corner_05.txt AC 96 ms 24484 KiB