結果
問題 | No.1295 木と駒 |
ユーザー |
👑 |
提出日時 | 2020-11-20 23:08:41 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,741 bytes |
コンパイル時間 | 982 ms |
コンパイル使用メモリ | 131,792 KB |
実行使用メモリ | 44,240 KB |
最終ジャッジ日時 | 2024-06-22 09:58:43 |
合計ジャッジ時間 | 12,844 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 WA * 28 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;(unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }int N;int[] A, B;int[][] G;int home(int u) {if (G[u].empty) {return -1;}const i = G[u][0];return A[i] ^ B[i] ^ u;}int[] par;// 0: come back, 1: goalias Result = int[2];Result[] dp, DP;void dfs(int u, int p) {par[u] = p;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != p) {dfs(v, u);}}// initResult[] rs;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != p) {// add dp[v]rs ~= dp[v];}}// calc dp[u]const len = cast(int)(rs.length);dp[u][0] = (p != -1 && p == home(u)) ? 1 : 0;foreach (j; 0 .. len) {dp[u][0] &= rs[j][0];}dp[u][1] = 1;if (len >= 1) {foreach (j; 0 .. len - 1) {dp[u][1] &= rs[j][0];}dp[u][1] &= rs[len - 1][1];}}void DFS(int u, int p) {// initalias Entry = Tuple!(Result, "r", int, "v");Entry[] es;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;/*if (v != p) {// add dp[v]}*/if (v != p) {es ~= Entry(dp[v], v);} else {es ~= Entry(DP[u], -1);}}/*if (p != -1) {// add DP[u]}*//*foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != p) {// calc DP[v], removing dp[v]}}*/const len = cast(int)(es.length);auto sums = new int[len + 1];foreach (j; 0 .. len) {sums[j + 1] = sums[j] + es[j].r[0];}foreach (j; 0 .. len) {const v = es[j].v;if (v != -1) {DP[v][0] = (home(u) == v) ? 1 : 0;DP[v][0] &= (sums[j] + (sums[len] - sums[j + 1]) >= len - 1) ? 1 : 0;DP[v][1] = 1;if (len - 1 >= 1) {if (j == len - 1) {DP[v][1] &= (sums[len - 2] >= len - 2) ? 1 : 0;DP[v][1] &= es[len - 2].r[1];} else {DP[v][1] &= (sums[j] + (sums[len - 1] - sums[j + 1]) >= len - 2) ? 1 : 0;DP[v][1] &= es[len - 1].r[1];}}}}foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != p) {DFS(v, u);}}}void main() {try {for (; ; ) {N = readInt();A = new int[N];B = new int[N];foreach (i; 0 .. N - 1) {A[i] = readInt() - 1;B[i] = readInt() - 1;}G = new int[][N];foreach (i; 0 .. N - 1) {G[A[i]] ~= i;G[B[i]] ~= i;}foreach (u; 0 .. N) {G[u].sort!((i0, i1) => ((A[i0] ^ B[i0] ^ u) < (A[i1] ^ B[i1] ^ u)));}debug {writeln("G = ", G);}const rt = 0;par = new int[N];dp = new Result[N];dfs(rt, -1);DP = new Result[N];DFS(rt, -1);debug {writeln("rt = ", rt);writeln("dp = ", dp);writeln("DP = ", DP);}foreach (u; 0 .. N) {// initResult[] rs;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;/*if (v != par[u]) {// add dp[v]}*/if (v != par[u]) {rs ~= dp[v];} else {rs ~= DP[u];}}/*if (u != rt) {// add DP[u]}*/debug {writeln(u, ": ", rs);}// calc ans, rooted at uconst len = cast(int)(rs.length);int ans = 1;if (len >= 1) {foreach (j; 0 .. len - 1) {ans &= rs[j][0];}ans &= rs[len - 1][1];}writeln(ans ? "Yes" : "No");}}} catch (EOFException e) {}}