結果

問題 No.363 門松サイクル
ユーザー 37zigen37zigen
提出日時 2016-06-13 12:46:51
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 4,987 bytes
コンパイル時間 2,669 ms
コンパイル使用メモリ 79,940 KB
実行使用メモリ 126,904 KB
最終ジャッジ日時 2024-04-17 19:06:25
合計ジャッジ時間 39,368 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 105 ms
52,816 KB
testcase_01 AC 120 ms
54,276 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 238 ms
58,748 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 110 ms
54,204 KB
testcase_25 AC 116 ms
54,296 KB
testcase_26 AC 1,904 ms
126,904 KB
testcase_27 AC 1,624 ms
125,728 KB
testcase_28 AC 2,082 ms
118,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.ArrayList;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		new Main().solve();
	}

	ArrayList<Integer> edges[];
	int[] A;
	void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		A = new int[N];
		for (int i = 0; i < N; i++)
			A[i] = sc.nextInt();
		edges = new ArrayList[N];
		for (int i = 0; i < N; i++)
			edges[i] = new ArrayList<Integer>();
		for (int i = 0; i < N - 1; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			edges[x].add(y);
			edges[y].add(x);
		}
		init(N);
		init2();

		int Q = sc.nextInt();
		for (int i = 0; i < Q; i++) {
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			int lca = lca(u, v);
			chi.clear();
			if(!isKado_seq(u,lca)){
				System.out.println("NO");
			}
			else if(!isKado_seq(v,lca)){
				System.out.println("NO");
			}
			else if(v!=lca&&!isKado(A[u],A[v],A[parent[0][v]])){
				System.out.println("NO");
			}
			else if(u!=lca&&!isKado(A[v],A[u],A[parent[0][u]])){
				System.out.println("NO");
			}else {
				if(chi.size()==1){
					if(lca!=u)chi.add(u);
					else if(lca!=v)chi.add(v);
					else throw new AssertionError("lcaの一方のみがuかvであるはず");
				}
				if(!isKado(A[chi.get(0)],A[lca],A[chi.get(1)])){
					System.out.println("NO");
				}else{
					System.out.println("YES");
				}
			}
		}
	}

	boolean isKado(int a, int b, int c) {
		if (a < 0 || b < 0 || c < 0)
			return false;
		if (a == b || b == c || c == a)
			return false;
		if (a < b && b > c)
			return true;
		if (a > b && b < c)
			return true;
		return false;
	}

	int MAX_LOG_V;// =(int)log2(MAX_V)+1
	int MAX_V;
	int root;// 根ノードの番号
	int parent[][];// [MAX_LOG_V + 1][MAX_V]
	// parent[k][v] 2^k回親を辿ったときに到達する頂点（根を通り過ぎたときは-1）
	int[] depth;// [MAX_V] 根からの深さ

	void init(int N) {
		// 変数の用意
		MAX_V = N;
		MAX_LOG_V = (int) (Math.log(MAX_V) / Math.log(2)) + 1;
		root = 0;
		parent = new int[MAX_LOG_V + 1][MAX_V];
		depth = new int[MAX_V];

		// parent[0]とdepthを初期化する
		dfs(root, -1, 0);
		// parentを初期化する
		for (int k = 0; k < MAX_LOG_V; k++) {
			for (int v = 0; v < MAX_V; v++) {
				if (parent[k][v] < 0) {
					parent[k + 1][v] = -1;
				} else {
					parent[k + 1][v] = parent[k][parent[k][v]];
				}
			}
		}
	}

	void dfs(int v, int p, int d) {
		parent[0][v] = p;
		depth[v] = d;
		for (int i = 0; i < edges[v].size(); i++) {
			if (edges[v].get(i) != p)
				dfs(edges[v].get(i), v, d + 1);
		}
	}

	int lca(int u, int v) {
		// uとvの深さが同じになるまで親を辿る
		if (depth[u] > depth[v]) {
			int d = u;
			u = v;
			v = d;
		}
		// depth[v]-depth[u]>=2^kとなる最小のkを求める。
		// つまりuをvと深さが同じか小さいぎりぎりのところまで親を辿る。
		for (int k = 0; k < MAX_LOG_V; k++) {
			if ((((depth[v] - depth[u]) >> k) & 1) == 1) {
				v = parent[k][v];
			}
		}
		if (u == v)
			return u;
		// uとvが衝突しないように辿る。
		for (int k = MAX_LOG_V - 1; k >= 0; k--) {
			if (parent[k][u] != parent[k][v] && parent[k][u] != -1 && parent[k][v] != -1) {
				u = parent[k][u];
				v = parent[k][v];
			}
		}
		return parent[0][u];
	}

	/*
	 * B[k]=1ならば A[k],A[k+1],A[k+2]が門松列であり、0なら門松列でない、とする。
	 * B[k]=1&&B[k+1]=1のときのみ、A[k],A[k+1],A[k+2],A[k+3]が門松列
	 * B[k]=1&&B[k+1]=1かつB[k+2]=1&&B[k+3]=1ならばA[k],A[k+1],A[k+2],A[k+3],A[k+4],A
	 * [k+5]が門松列。
	 * C[0][k]=B[k]
	 * C[1][k]=C[0][[k]&C[0][k+1]
	 * C[2][k]=C[1][k]&C[1][k+2]
	 * C[3][k]=C[2][k]&C[2][k+4]
	 * C[4][k]=C[3][k]&C[3][k+8]
	 * C[v][k]=C[v-1][k]&C[v-1][k+2^(v-1)] と次々に定義する。 このとき、C[v][k]=1であることと
	 * A[k],...,A[k+2^v+2] が門松列であることは同値である。
	 */
	int[][] C;

	void init2() {
		// 変数の用意
		C = new int[MAX_LOG_V + 1][MAX_V];

		// C[0]を初期化する
		for (int i = 0; i < MAX_V; i++) {
			int p1 = parent[0][i];
			if(p1==-1)continue;
			int p2 = parent[0][p1];
			if(p2==-1)continue;
			if (isKado(A[i], A[p1], A[p2])) {
				C[0][i] = 1;
			}
		}
		// Cを初期化する
		for (int v = 0; v < MAX_LOG_V; v++) {
			for (int k = 0; k < MAX_V; k++) {
				if((k + (int) Math.pow(2, v))>=MAX_V)continue;
				C[v + 1][k] = C[v][k] & C[v][k + (int) Math.pow(2, v)];
			}
		}
	}

	boolean isKado_seq(int c, int p) {
		int d = depth[c] - (depth[p] + 2);
		if (d == -1) {
			chi.add(c);
			return true;
		}
		if(d==-2){
			return true;
		}
		if (C[0][c] == 0)
			return false;
		for (int i = 0; d > 0; d >>= 1, i++) {
			if ((d & 1) == 1) {
				c = parent[i][c];
				int judge = C[i][c];
				if (judge == 0)
					return false;
			}
		}
		if (parent[0][parent[0][c]] != p)
			throw new AssertionError("c!=p");
		chi.add(parent[0][c]);
		return true;
	}

	ArrayList<Integer> chi = new ArrayList<Integer>();
}
0