結果
問題 | No.363 門松サイクル |
ユーザー |
|
提出日時 | 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 |
ソースコード
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]);}}