#188334 (D) No.363 門松サイクル

提出ソース

結果

問題	No.363 門松サイクル
ユーザー	te-sh
提出日時	2017-07-13 16:05:12
言語	D (dmd 2.106.1)
結果	AC
実行時間	337 ms / 4,000 ms
コード長	5,827 bytes
コンパイル時間	975 ms
コンパイル使用メモリ	118,828 KB
実行使用メモリ	39,928 KB
最終ジャッジ日時	2024-06-12 20:55:00
合計ジャッジ時間	6,873 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	4 ms 6,940 KB
testcase_03	AC	3 ms 6,940 KB
testcase_04	AC	3 ms 6,944 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	3 ms 6,944 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	4 ms 6,940 KB
testcase_09	AC	100 ms 18,212 KB
testcase_10	AC	121 ms 19,228 KB
testcase_11	AC	209 ms 35,724 KB
testcase_12	AC	229 ms 32,712 KB
testcase_13	AC	274 ms 31,224 KB
testcase_14	AC	224 ms 27,648 KB
testcase_15	AC	211 ms 32,424 KB
testcase_16	AC	124 ms 23,296 KB
testcase_17	AC	216 ms 39,736 KB
testcase_18	AC	335 ms 30,576 KB
testcase_19	AC	253 ms 32,744 KB
testcase_20	AC	337 ms 32,376 KB
testcase_21	AC	232 ms 37,768 KB
testcase_22	AC	302 ms 30,980 KB
testcase_23	AC	182 ms 33,248 KB
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	181 ms 39,928 KB
testcase_27	AC	183 ms 39,184 KB
testcase_28	AC	209 ms 34,644 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

void main()
{
  auto n = readln.chomp.to!size_t;

  auto a = new int[](n), rd1 = readln.chomp.splitter(' ');
  foreach (i; 0..n) {
    a[i] = rd1.front.to!int;
    rd1.popFront();
  }

  auto isKadomatsu(size_t i1, size_t i2, size_t i3)
  {
    auto v1 = a[i1], v2 = a[i2], v3 = a[i3];
    return v1 != v2 && v2 != v3 && v3 != v1 && (v1 > v2 && v3 > v2 || v1 < v2 && v3 < v2);
  }

  auto tree = Tree(n);

  foreach (_; 0..n-1) {
    auto rd2 = readln.chomp.splitter(' ');
    auto u = rd2.front.to!size_t-1;
    rd2.popFront();
    auto v = rd2.front.to!size_t-1;
    tree.addEdge(u, v);
  }

  tree.rootify(0);
  tree.makePath(0);

  auto pathKadomatsu = new SparseTable!(bool, "a & b")[](tree.paths.length);
  foreach (i, path; tree.paths) {
    auto pl = path.length;
    if (pl >= 3) {
      auto b = new bool[](pl-2);
      foreach (j; 0..pl-2)
        b[j] = isKadomatsu(path[j], path[j+1], path[j+2]);
      pathKadomatsu[i] = SparseTable!(bool, "a & b")(b);
    }
  }

  struct AKR { bool r; size_t uchild; }

  auto allKadomatsu(size_t u, size_t v)
  {
    size_t head;

    while (tree.path[u] != tree.path[v]) {
      auto pathNo = tree.path[v], path = tree.paths[pathNo];
      auto d = tree.depthInPath(v);

      head = path[0];
      auto headParent = tree.parent[head];

      if (d >= 2 && !pathKadomatsu[pathNo][0..d-1] ||
          path.length >= 2 && d >= 1 && !isKadomatsu(headParent, head, path[1]) ||
          headParent != u && !isKadomatsu(tree.parent[headParent], headParent, head)) {
        return AKR(false, 0);
      }

      v = headParent;
    }

    auto pathNo = tree.path[v], path = tree.paths[pathNo];
    auto d1 = tree.depthInPath(u), d2 = tree.depthInPath(v);
    if (d2 - d1 >= 2 && !pathKadomatsu[pathNo][d1..d2-1])
      return AKR(false, 0);

    return AKR(true, u == v ? head : path[d1+1]);
  }

  auto calc(size_t u, size_t v)
  {
    auto lca = tree.lca(u, v);
    if (lca == v) swap(u, v);

    if (tree.parent[v] == u) return false;

    if (lca == u) {
      auto r = allKadomatsu(u, v);

      if (!r.r ||
          !isKadomatsu(tree.parent[v], v, u) ||
          !isKadomatsu(v, u, r.uchild))
        return false;

      return true;
    } else {
      auto r1 = allKadomatsu(lca, u);
      auto r2 = allKadomatsu(lca, v);

      if (!r1.r || !r2.r ||
          !isKadomatsu(r1.uchild, lca, r2.uchild) ||
          !isKadomatsu(tree.parent[u], u, v) ||
          !isKadomatsu(u, v, tree.parent[v]))
        return false;

      return true;
    }
  }

  auto q = readln.chomp.to!size_t;
  foreach (_; 0..q) {
    auto rd3 = readln.chomp.splitter;
    auto u = rd3.front.to!size_t-1;
    rd3.popFront();
    auto v = rd3.front.to!size_t-1;
    writeln(calc(u, v) ? "YES" : "NO");
  }
}

struct Tree
{
  import std.container;

  size_t n;
  size_t[][] adj;
  int[] size, depth;
  size_t[] head, parent, path;
  size_t[][] paths;

  this(size_t n)
  {
    this.n = n;
    adj = new size_t[][](n);
  }

  auto addEdge(size_t s, size_t t)
  {
    adj[s] ~= t;
    adj[t] ~= s;
  }

  auto rootify(size_t r)
  {
    parent = new size_t[](n);
    depth = new int[](n);
    depth[] = -1;

    struct UP { size_t u, p; }
    auto st1 = SList!UP(UP(r, r));
    auto st2 = SList!UP();
    while (!st1.empty) {
      auto up = st1.front, u = up.u, p = up.p; st1.removeFront();

      parent[u] = p;
      depth[u] = depth[p] + 1;

      foreach (v; adj[u])
        if (v != p) {
          st1.insertFront(UP(v, u));
          st2.insertFront(UP(v, u));
        }
    }

    size = new int[](n);
    size[] = 1;

    while (!st2.empty) {
      auto up = st2.front, u = up.u, p = up.p; st2.removeFront();
      size[p] += size[u];
    }

    head = new size_t[](n);
    head[] = n;

    struct US { size_t u, s; }
    auto st = SList!US(US(r, r));

    while (!st.empty) {
      auto us = st.front, u = us.u, s = us.s; st.removeFront();

      head[u] = s;
      auto z = n;
      foreach (v; adj[u])
        if (head[v] == n && (z == n || size[z] < size[v])) z = v;

      foreach (v; adj[u])
        if (head[v] == n) st.insertFront(US(v, v == z ? s : v));
    }
  }

  auto makePath(size_t r)
  {
    auto pathIndex = 0;
    path = new size_t[](n);

    auto q = DList!size_t(r);

    while (!q.empty) {
      auto u = q.front; q.removeFront();

      if (u == head[u]) {
        path[u] = pathIndex++;
        paths ~= [u];
      } else {
        path[u] = path[head[u]];
        paths[path[u]] ~= u;
      }

      foreach (v; adj[u])
        if (v != parent[u]) q.insertBack(v);
    }
  }

  auto depthInPath(size_t n)
  {
    return depth[n] - depth[head[n]];
  }

  auto lca(size_t u, size_t v)
  {
    while (head[u] != head[v])
      if (depth[head[u]] < depth[head[v]]) v = parent[head[v]];
      else                                 u = parent[head[u]];
    return depth[u] < depth[v] ? u : v;
  }
}

struct SparseTable(T, alias pred = "a < b ? a : b")
{
  import std.algorithm, std.functional;
  alias predFun = binaryFun!pred;

  size_t[] logTable;
  size_t[][] rmq;
  size_t n;
  T[] a;

  this(T[] a)
  {
    this.a = a;
    this.n = a.length;

    logTable = new size_t[n + 1];
    foreach (i; 2..n+1)
      logTable[i] = logTable[i >> 1] + 1;

    rmq = new size_t[][](logTable[n] + 1, n);

    foreach (i; 0..n)
      rmq[0][i] = i;

    for (size_t k = 1; (1 << k) < n; ++k)
      for (size_t i = 0; i + (1 << k) <= n; ++i) {
        auto x = rmq[k - 1][i];
        auto y = rmq[k - 1][i + (1 << k - 1)];
        rmq[k][i] = predFun(a[x], a[y]) == a[x] ? x : y;
      }
  }

  pure size_t opDollar() const { return n; }

  pure T opSlice(size_t l, size_t r) const
  {
    auto k = logTable[r - l - 1];
    auto x = rmq[k][l];
    auto y = rmq[k][r - (1 << k)];
    return predFun(a[x], a[y]);
  }
}

yukicoder

結果

テストケース

ソースコード