Submission #38398017

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  int u[M], v[M];
  for (int m = 0; m < M; ++m) {
    cin >> u[m] >> v[m];
    --u[m];
    --v[m];
  }
  if (N - M != 1) {
    cout << "No" << endl;
    return 0;
  }
  int link[N];
  for (int n = 0; n < N; ++n) link[n] = -1;
  for (int m = 0; m < M; ++m) {
    int U = u[m], V = v[m];
    if (link[U] == -2 || link[V] == -2) {
      cout << "No" << endl;
      return 0;
    }
    if (link[U] == -1) {
      if (link[V] == -1) {
        link[U] = V;
        link[V] = U;
      } else {
        link[link[V]] = U;
        link[U] = link[V];
        link[V] = -2;
      }
    } else {
      if (link[V] == -1) {
        link[link[U]] = V;
        link[V] = link[U];
        link[U] = -2;
      } else {
        if (link[U] == V) {
          cout << "No" << endl;
          return 0;
        }
        link[link[U]] = link[V];
        link[link[V]] = link[U];
        link[U] = -2;
        link[V] = -2;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Submission Info

Submission Time
Task C - Path Graph?
User Steinberg
Language C++ (GCC 9.2.1)
Score 300
Code Size 1099 Byte
Status AC
Exec Time 90 ms
Memory 5936 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 36
Set Name Test Cases
Sample 00_example_00.txt, 00_example_01.txt, 00_example_02.txt
All 00_example_00.txt, 00_example_01.txt, 00_example_02.txt, 01_dense_00.txt, 02_path_00.txt, 02_path_01.txt, 02_path_02.txt, 02_path_03.txt, 02_path_04.txt, 02_path_05.txt, 02_path_06.txt, 02_path_07.txt, 02_path_08.txt, 02_path_09.txt, 03_paths_00.txt, 03_paths_01.txt, 03_paths_02.txt, 04_cycles_00.txt, 04_cycles_01.txt, 04_cycles_02.txt, 04_cycles_03.txt, 04_cycles_04.txt, 04_cycles_05.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, 06_random_00.txt, 06_random_01.txt, 06_random_02.txt, 06_random_03.txt, 06_random_04.txt, 07_small_00.txt, 07_small_01.txt
Case Name Status Exec Time Memory
00_example_00.txt AC 6 ms 3348 KiB
00_example_01.txt AC 2 ms 3492 KiB
00_example_02.txt AC 3 ms 3512 KiB
01_dense_00.txt AC 40 ms 4252 KiB
02_path_00.txt AC 88 ms 5836 KiB
02_path_01.txt AC 88 ms 5876 KiB
02_path_02.txt AC 43 ms 4420 KiB
02_path_03.txt AC 68 ms 5300 KiB
02_path_04.txt AC 42 ms 4536 KiB
02_path_05.txt AC 74 ms 5528 KiB
02_path_06.txt AC 36 ms 4332 KiB
02_path_07.txt AC 77 ms 5556 KiB
02_path_08.txt AC 40 ms 4420 KiB
02_path_09.txt AC 4 ms 3456 KiB
03_paths_00.txt AC 88 ms 4896 KiB
03_paths_01.txt AC 84 ms 4992 KiB
03_paths_02.txt AC 46 ms 4292 KiB
04_cycles_00.txt AC 86 ms 5056 KiB
04_cycles_01.txt AC 86 ms 4944 KiB
04_cycles_02.txt AC 89 ms 4904 KiB
04_cycles_03.txt AC 88 ms 5040 KiB
04_cycles_04.txt AC 84 ms 5040 KiB
04_cycles_05.txt AC 40 ms 4132 KiB
05_corner_00.txt AC 86 ms 5856 KiB
05_corner_01.txt AC 86 ms 5904 KiB
05_corner_02.txt AC 89 ms 5900 KiB
05_corner_03.txt AC 90 ms 5936 KiB
05_corner_04.txt AC 86 ms 5756 KiB
05_corner_05.txt AC 85 ms 5848 KiB
06_random_00.txt AC 85 ms 4976 KiB
06_random_01.txt AC 87 ms 5056 KiB
06_random_02.txt AC 89 ms 5056 KiB
06_random_03.txt AC 85 ms 5092 KiB
06_random_04.txt AC 84 ms 5076 KiB
07_small_00.txt AC 2 ms 3592 KiB
07_small_01.txt AC 2 ms 3348 KiB