結果

問題 No.363 門松サイクル
ユーザー te-sh
提出日時 2017-07-13 16:05:12
言語 D
(dmd 2.109.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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