#98995 (Java21) No.386 貪欲な領主

提出ソース

結果

問題	No.386 貪欲な領主
ユーザー	37zigen
提出日時	2016-06-19 20:12:56
言語	Java21 (openjdk 21)
結果	RE
実行時間	-
コード長	7,828 bytes
コンパイル時間	3,153 ms
コンパイル使用メモリ	83,440 KB
実行使用メモリ	50,452 KB
最終ジャッジ日時	2024-10-12 03:43:57
合計ジャッジ時間	7,992 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	TLE	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package yukicoder;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
public class Main {
	public static void main(String[] args) {
		 new Main().solve();
	}

	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();
		Printer pr=new Printer(System.out);
		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)) {
				pr.println("NO");
			} else if (!isKado_seq(v, lca)) {
				pr.println("NO");
			} else if (v != lca && !isKado(A[u], A[v], A[parent[0][v]])) {
				pr.println("NO");
			} else if (u != lca && !isKado(A[v], A[u], A[parent[0][u]])) {
				pr.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)])) {
					pr.println("NO");
				} else {
					pr.println("YES");
				}
			}
		}
		pr.close();
	}


	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;
		}
	}
	private static class Scanner{
		BufferedReader br;
		Iterator<String> it;
		Scanner(InputStream in){
			br=new BufferedReader(new InputStreamReader(in));
		}
		String next()throws RuntimeException{
			try{
				if(it==null||!it.hasNext())
					it=Arrays.asList(br.readLine().split(" ")).iterator();
				return it.next();
			}catch(IOException e){
				throw new IllegalStateException();
			}
		}
		int nextInt() throws RuntimeException{
			return Integer.parseInt(next());
		}
		long nextLong() throws RuntimeException{
			return Long.parseLong(next());
		}
		double nextDouble() throws RuntimeException{
			return Double.parseDouble(next());
		}
		void close(){
			try{
				br.close();
			}catch(IOException e){
				throw new IllegalStateException();
			}
		}
	}
	private static class Printer extends PrintWriter{
		Printer(PrintStream out){
			super(out);
		}
	}
	
}