結果

問題 No.363 門松サイクル
ユーザー te-shte-sh
提出日時 2017-07-13 16:05:12
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 385 ms / 4,000 ms
コード長 5,827 bytes
コンパイル時間 995 ms
コンパイル使用メモリ 102,000 KB
実行使用メモリ 41,156 KB
最終ジャッジ日時 2023-09-03 15:11:51
合計ジャッジ時間 7,449 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 4 ms
4,384 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 4 ms
4,384 KB
testcase_06 AC 4 ms
4,896 KB
testcase_07 AC 4 ms
4,380 KB
testcase_08 AC 5 ms
4,380 KB
testcase_09 AC 111 ms
18,748 KB
testcase_10 AC 127 ms
18,528 KB
testcase_11 AC 238 ms
37,096 KB
testcase_12 AC 262 ms
34,396 KB
testcase_13 AC 320 ms
30,904 KB
testcase_14 AC 248 ms
27,152 KB
testcase_15 AC 221 ms
33,488 KB
testcase_16 AC 140 ms
24,116 KB
testcase_17 AC 247 ms
41,156 KB
testcase_18 AC 385 ms
31,148 KB
testcase_19 AC 285 ms
34,288 KB
testcase_20 AC 375 ms
33,412 KB
testcase_21 AC 256 ms
38,112 KB
testcase_22 AC 326 ms
31,904 KB
testcase_23 AC 197 ms
33,464 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 204 ms
39,528 KB
testcase_27 AC 202 ms
40,096 KB
testcase_28 AC 233 ms
36,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]);
  }
}
0