Submission #1795640


Source Code Expand

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto rd = readln.split.to!(int[]), n = rd[0], q = rd[1];

  auto uf = UnionFind!int(n), eo = new bool[](n);
  foreach (_; 0..q) {
    auto rd2 = readln.splitter;
    auto w = rd2.front.to!int; rd2.popFront();
    auto x = rd2.front.to!int-1; rd2.popFront();
    auto y = rd2.front.to!int-1; rd2.popFront();
    auto z = rd2.front.to!int%2 == 0;

    auto px = uf[x], py = uf[y];
    if (w == 1) {
      if (px == py) {
        if (z && eo[x] != eo[y] || !z && eo[x] == eo[y])
          uf.superForest[px] = true;
      } else {
        if (z && eo[x] != eo[y] || !z && eo[x] == eo[y]) {
          foreach (i; uf.countNodes[px] > uf.countNodes[py] ? uf.nodes[py] : uf.nodes[px])
            eo[i] = !eo[i];
        }
        uf.unite(x, y);
      }
    } else {
      writeln(px == py && (eo[x] == eo[y] || uf.superForest[px]) ? "YES" : "NO");
    }
  }
}

struct UnionFind(T)
{
  import std.algorithm, std.range;

  T[] p; // parent
  const T s; // sentinel
  const T n;
  T countForests; // number of forests
  T[] countNodes; // number of nodes in forests

  T[][] nodes;
  bool[] superForest;

  this(T n)
  {
    this.n = n;
    s = n;
    p = new T[](n);
    p[] = s;
    countForests = n;
    countNodes = new T[](n);
    countNodes[] = 1;

    nodes = new T[][](n);
    foreach (i; 0..n) nodes[i] = [i];
    superForest = new bool[](n);
  }

  T opIndex(T i)
  {
    if (p[i] == s) {
      return i;
    } else {
      p[i] = this[p[i]];
      return p[i];
    }
  }

  bool unite(T i, T j)
  {
    auto pi = this[i], pj = this[j];
    if (pi != pj) {
      p[pj] = pi;
      --countForests;

      if (countNodes[pi] > countNodes[pj]) {
        nodes[pi] ~= nodes[pj];
      } else {
        nodes[pj] ~= nodes[pi];
        nodes[pi] = nodes[pj];
      }
      nodes[pj] = [];

      superForest[pi] |= superForest[pj];

      countNodes[pi] += countNodes[pj];
      return true;
    } else {
      return false;
    }
  }

  auto countNodesOf(T i) { return countNodes[this[i]]; }
  bool isSame(T i, T j) { return this[i] == this[j]; }

  auto groups()
  {
    auto g = new T[][](n);
    foreach (i; 0..n) g[this[i]] ~= i;
    return g.filter!(l => !l.empty);
  }
}

Submission Info

Submission Time
Task D - 偶数メートル
User tesh
Language D (DMD64 v2.070.1)
Score 100
Code Size 2361 Byte
Status AC
Exec Time 103 ms
Memory 13564 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 32
AC × 62
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 2 ms 380 KB
subtask1_02.txt AC 2 ms 256 KB
subtask1_03.txt AC 3 ms 380 KB
subtask1_04.txt AC 2 ms 256 KB
subtask1_05.txt AC 2 ms 380 KB
subtask1_06.txt AC 2 ms 380 KB
subtask1_07.txt AC 2 ms 256 KB
subtask1_08.txt AC 3 ms 380 KB
subtask1_09.txt AC 3 ms 508 KB
subtask1_10.txt AC 3 ms 508 KB
subtask1_11.txt AC 3 ms 508 KB
subtask1_12.txt AC 3 ms 508 KB
subtask1_13.txt AC 3 ms 508 KB
subtask1_14.txt AC 3 ms 508 KB
subtask1_15.txt AC 3 ms 508 KB
subtask1_16.txt AC 3 ms 508 KB
subtask1_17.txt AC 3 ms 508 KB
subtask1_18.txt AC 3 ms 508 KB
subtask1_19.txt AC 3 ms 508 KB
subtask1_20.txt AC 3 ms 508 KB
subtask1_21.txt AC 3 ms 508 KB
subtask1_22.txt AC 3 ms 508 KB
subtask1_23.txt AC 4 ms 2556 KB
subtask1_24.txt AC 3 ms 508 KB
subtask1_25.txt AC 3 ms 508 KB
subtask1_26.txt AC 3 ms 508 KB
subtask1_27.txt AC 3 ms 508 KB
subtask1_28.txt AC 3 ms 508 KB
subtask1_29.txt AC 3 ms 508 KB
subtask2_01.txt AC 29 ms 1916 KB
subtask2_02.txt AC 74 ms 7932 KB
subtask2_03.txt AC 8 ms 1788 KB
subtask2_04.txt AC 69 ms 6268 KB
subtask2_05.txt AC 39 ms 7932 KB
subtask2_06.txt AC 38 ms 5756 KB
subtask2_07.txt AC 69 ms 7548 KB
subtask2_08.txt AC 75 ms 8956 KB
subtask2_09.txt AC 47 ms 5500 KB
subtask2_10.txt AC 89 ms 9468 KB
subtask2_11.txt AC 86 ms 9852 KB
subtask2_12.txt AC 89 ms 9724 KB
subtask2_13.txt AC 90 ms 9212 KB
subtask2_14.txt AC 91 ms 10236 KB
subtask2_15.txt AC 87 ms 9596 KB
subtask2_16.txt AC 87 ms 10364 KB
subtask2_17.txt AC 88 ms 10364 KB
subtask2_18.txt AC 99 ms 10236 KB
subtask2_19.txt AC 87 ms 9596 KB
subtask2_20.txt AC 86 ms 9340 KB
subtask2_21.txt AC 99 ms 11132 KB
subtask2_22.txt AC 101 ms 12412 KB
subtask2_23.txt AC 100 ms 10748 KB
subtask2_24.txt AC 100 ms 11004 KB
subtask2_25.txt AC 102 ms 10748 KB
subtask2_26.txt AC 103 ms 10876 KB
subtask2_27.txt AC 101 ms 11004 KB
subtask2_28.txt AC 100 ms 10748 KB
subtask2_29.txt AC 101 ms 13564 KB
subtask2_30.txt AC 76 ms 10236 KB