結果

問題 No.363 門松サイクル
ユーザー 37zigen37zigen
提出日時 2016-06-13 22:49:50
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,605 ms / 4,000 ms
コード長 8,492 bytes
コンパイル時間 2,912 ms
コンパイル使用メモリ 83,164 KB
実行使用メモリ 97,956 KB
最終ジャッジ日時 2024-10-09 13:30:12
合計ジャッジ時間 45,590 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 135 ms
41,400 KB
testcase_01 AC 134 ms
41,820 KB
testcase_02 AC 294 ms
47,616 KB
testcase_03 AC 282 ms
47,528 KB
testcase_04 AC 291 ms
47,740 KB
testcase_05 AC 293 ms
47,796 KB
testcase_06 AC 302 ms
47,840 KB
testcase_07 AC 299 ms
47,704 KB
testcase_08 AC 310 ms
47,560 KB
testcase_09 AC 1,454 ms
74,196 KB
testcase_10 AC 1,467 ms
76,148 KB
testcase_11 AC 2,042 ms
94,940 KB
testcase_12 AC 2,300 ms
91,872 KB
testcase_13 AC 2,251 ms
92,900 KB
testcase_14 AC 2,065 ms
91,848 KB
testcase_15 AC 1,930 ms
93,304 KB
testcase_16 AC 1,727 ms
79,332 KB
testcase_17 AC 2,359 ms
95,664 KB
testcase_18 AC 2,605 ms
95,788 KB
testcase_19 AC 2,251 ms
96,724 KB
testcase_20 AC 2,522 ms
95,536 KB
testcase_21 AC 2,527 ms
96,344 KB
testcase_22 AC 2,447 ms
94,688 KB
testcase_23 AC 2,137 ms
92,476 KB
testcase_24 AC 132 ms
41,552 KB
testcase_25 AC 143 ms
41,684 KB
testcase_26 AC 2,131 ms
97,956 KB
testcase_27 AC 2,180 ms
97,132 KB
testcase_28 AC 2,336 ms
97,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		 new Main().solve();
//		int c = 0;
//		while (true) {
//			new Q363().build();
//			String s1 = new Q363().solve_trial();
//			String s2 = "";
//			try {
//				s2 = new sample().run(N, A, X, Y);
//			} catch (Exception e) {
//				// TODO 自動生成された catch ブロック
//				e.printStackTrace();
//			}
//			c++;
//			if (!s1.equals(s2)) {
//				System.out.println(N);
//				for (int i = 0; i < N; i++) {
//					System.out.print(A[i] + " ");
//				}
//				System.out.println();
//				for (int i = 0; i < N - 1; i++) {
//					System.out.println(X[i] + " " + Y[i]);
//				}
//				System.out.println(s1 + " " + s2);
//				break;
//			}
//			System.out.println(c);
//		}
//		System.out.println("試行回数" + c);
	}

	ArrayList<Integer> edges[];

	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");
				}
			}
		}
	}

	String solve_trial() {
		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 = X[i] - 1;
			int y = Y[i] - 1;
			edges[x].add(y);
			edges[y].add(x);
		}
		init(N);
		init2();

		int Q = 1;
		for (int i = 0; i < Q; i++) {
			int u = 1 - 1;
			int v = 2 - 1;
			int lca = lca(u, v);
			chi.clear();
			if (!isKado_seq(u, lca)) {
				return "NO";
			} else if (!isKado_seq(v, lca)) {
				return "NO";
			} else if (v != lca && !isKado(A[u], A[v], A[parent[0][v]])) {
				return "NO";
			} else if (u != lca && !isKado(A[v], A[u], A[parent[0][u]])) {
				return "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)])) {
					return "NO";
				} else {
					return "YES";
				}
			}
		}
		return "Error";
	}

	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を初期化する
		bfs(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]];
				}
			}
		}
	}
	class P{
		int parent;
		int me;
		int depth;
		P(int me,int parent,int depth){
			this.me=me;
			this.parent=parent;
			this.depth=depth;
		}
	}
	void bfs(int v, int p, int d) {
		ArrayDeque<P> q=new ArrayDeque<P>();
		q.add(new P(v,p,d));
		while(!q.isEmpty()){
			P u=q.poll();
			parent[0][u.me]=u.parent;
			depth[u.me]=u.depth;
			for (int i = 0; i < edges[u.me].size(); i++) {
				if (edges[u.me].get(i) != u.parent)
					q.add(new P(edges[u.me].get(i), u.me, u.depth + 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 (parent[v][k]==-1)
					continue;
				C[v + 1][k] = C[v][k] & C[v][parent[v][k]];
			}
		}
	}

	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) {
				int judge = C[i][c];
				if (judge == 0) {
					return false;
				}
				c = parent[i][c];
				
				if (C[0][c] == 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>();

	static int N;
	static int[] A;
	static int[] X;
	static int[] Y;

	void build() {
		int max = 50000;
		N = (int) (Math.random() * max) + 3;// 頂点数
		A = new int[N];
		X = new int[N - 1];
		Y = new int[N - 1];
		for (int i = 0; i < N; i++) {
			A[i] = (int) (Math.random() * 10000) + 1;
		}
		DJSet ds = new DJSet(N);

		// 0-indexedで接続されている頂点を表示
		int count = 0;
		while (ds.count() != 1) {
			int x = (int) (Math.random() * N);
			int y = (int) (Math.random() * N);
			if (ds.equiv(x, y))
				continue;
			else {
				X[count] = x + 1;
				Y[count] = y + 1;
				count++;
				ds.setUnion(x, y);
			}
		}
	}

	class DJSet {
		int n;// the number of vertices
		int[] d;

		DJSet(int n) {
			this.n = n;
			d = new int[n];
			Arrays.fill(d, -1);
		}

		int root(int x) {
			return d[x] < 0 ? x : root(d[x]);
		}

		boolean setUnion(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (x < y) {
					int d = x;
					x = y;
					y = d;
				}
				// x>y
				d[y] += d[x];
				d[x] = y;
			}
			return x != y;
		}

		boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		// xを含む木のNodeの数
		int size(int x) {
			return d[root(x)] * (-1);
		}

		// 連結グラフの数
		int count() {
			int ct = 0;
			for (int u : d) {
				if (u < 0)
					ct++;
			}
			return ct;
		}
	}
}
0