結果

問題 No.1030 だんしんぐぱーりない
ユーザー ks2mks2m
提出日時 2020-04-17 22:50:41
言語 Java21
(openjdk 21)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,501 bytes
コンパイル時間 4,053 ms
コンパイル使用メモリ 91,524 KB
実行使用メモリ 97,348 KB
最終ジャッジ日時 2024-04-14 15:07:32
合計ジャッジ時間 53,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
50,552 KB
testcase_01 AC 59 ms
50,680 KB
testcase_02 AC 60 ms
50,620 KB
testcase_03 AC 60 ms
50,660 KB
testcase_04 AC 61 ms
50,636 KB
testcase_05 AC 1,723 ms
83,016 KB
testcase_06 AC 1,389 ms
79,900 KB
testcase_07 AC 1,167 ms
68,652 KB
testcase_08 AC 1,092 ms
67,228 KB
testcase_09 AC 1,281 ms
79,900 KB
testcase_10 AC 800 ms
63,548 KB
testcase_11 AC 1,703 ms
71,392 KB
testcase_12 AC 1,301 ms
77,660 KB
testcase_13 AC 1,194 ms
78,836 KB
testcase_14 AC 1,436 ms
74,148 KB
testcase_15 AC 1,004 ms
66,400 KB
testcase_16 AC 1,297 ms
71,176 KB
testcase_17 AC 1,409 ms
80,536 KB
testcase_18 AC 1,685 ms
74,740 KB
testcase_19 AC 1,092 ms
67,012 KB
testcase_20 AC 1,174 ms
72,040 KB
testcase_21 AC 1,356 ms
69,744 KB
testcase_22 AC 1,149 ms
72,044 KB
testcase_23 AC 1,416 ms
69,636 KB
testcase_24 AC 1,230 ms
67,820 KB
testcase_25 AC 1,346 ms
69,044 KB
testcase_26 AC 954 ms
61,996 KB
testcase_27 AC 1,065 ms
66,056 KB
testcase_28 AC 1,387 ms
78,768 KB
testcase_29 AC 1,129 ms
77,024 KB
testcase_30 AC 1,057 ms
71,452 KB
testcase_31 AC 1,185 ms
70,608 KB
testcase_32 AC 1,404 ms
80,296 KB
testcase_33 AC 1,366 ms
79,680 KB
testcase_34 AC 830 ms
64,416 KB
testcase_35 AC 1,956 ms
95,188 KB
testcase_36 AC 1,921 ms
96,952 KB
testcase_37 TLE -
testcase_38 TLE -
testcase_39 AC 1,889 ms
95,036 KB
testcase_40 AC 71 ms
50,376 KB
testcase_41 AC 59 ms
50,308 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiFunction;

public class Main {
	static int[] c;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int k = Integer.parseInt(sa[1]);
		int q = Integer.parseInt(sa[2]);

		sa = br.readLine().split(" ");
		c = new int[n];
		for (int i = 0; i < n; i++) {
			c[i] = Integer.parseInt(sa[i]);
		}

		sa = br.readLine().split(" ");
		int[] a = new int[k];
		for (int i = 0; i < k; i++) {
			a[i] = Integer.parseInt(sa[i]) - 1;
		}

		List<List<Integer>> list = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; i++) {
			sa = br.readLine().split(" ");
			int e = Integer.parseInt(sa[0]) - 1;
			int f = Integer.parseInt(sa[1]) - 1;
			list.get(e).add(f);
			list.get(f).add(e);
		}
		SegTreeLCA lca = new SegTreeLCA(n, list, 0);
		SegTree<Integer> st = new SegTree<Integer>(k, -1, (o1, o2) -> {
			if (o1 == -1) return o2;
			if (o2 == -1) return o1;
			return lca.lca(o1, o2).i;
		});
		for (int i = 0; i < k; i++) {
			st.update(i, a[i]);
		}

		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			sa = br.readLine().split(" ");
			if (sa[0].equals("1")) {
				int x = Integer.parseInt(sa[1]) - 1;
				int y = Integer.parseInt(sa[2]) - 1;
				st.update(x, y);
			} else {
				int l = Integer.parseInt(sa[1]) - 1;
				int r = Integer.parseInt(sa[2]);
				pw.println(lca.get(st.query(l, r)).c);
			}
		}
		pw.flush();
		br.close();
	}

	static class SegTreeLCA {
		int n = 2;
		int n2, idx;
		Obj[] arr;
		int[] first;
		Obj INF = new Obj(-1, Integer.MAX_VALUE, 0);

		/**
		 * 初期化
		 * @param size 頂点数
		 * @param list 隣接リスト
		 * @param root 根の頂点番号
		 */
		public SegTreeLCA(int size, List<List<Integer>> list, int root) {
			while (n < size) {
				n <<= 1;
			}
			n <<= 1;
			n2 = n * 2 - 1;
			idx = n - 1;
			arr = new Obj[n2];
			first = new int[size];
			Arrays.fill(first, -1);

			Obj r = new Obj(root, 0, c[root]);
			arr[idx] = r;
			first[root] = idx - n + 1;
			idx++;
			dfs(list, r, -1);
			for (int i = idx; i < n2; i++) {
				arr[i] = INF;
			}
			for (int i = n - 2; i >= 0; i--) {
				if (arr[i * 2 + 1].dep < arr[i * 2 + 2].dep) {
					arr[i] = arr[i * 2 + 1];
				} else {
					arr[i] = arr[i * 2 + 2];
				}
			}
		}

		private void dfs(List<List<Integer>> list, Obj cur, int p) {
			for (int ch : list.get(cur.i)) {
				if (ch != p) {
					int cmax = Math.max(cur.c, c[ch]);
					Obj o = new Obj(ch, cur.dep + 1, cmax);
					arr[idx] = o;
					if (first[ch] == -1) {
						first[ch] = idx - n + 1;
					}
					idx++;
					dfs(list, o, cur.i);
					arr[idx] = cur;
					idx++;
				}
			}
		}

		/**
		 * 頂点Iのオブジェクト取得（0≦I＜size）
		 */
		public Obj get(int i) {
			return arr[first[i] + n - 1];
		}

		/**
		 * 頂点A,BのLCA取得（0≦A,B＜size）
		 */
		public Obj lca(int a, int b) {
			int l = Math.min(first[a], first[b]);
			int r = Math.max(first[a], first[b]);
			return query(l, r + 1, 0, 0, n);
		}
		private Obj query(int l, int r, int k, int beg, int end) {
			if (end <= l || r <= beg) return INF; // 交差しない
			if (l <= beg && end <= r) return arr[k]; // 完全に含む
			Obj o1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
			Obj o2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
			if (o1.dep < o2.dep) {
				return o1;
			}
			return o2;
		}

		private static class Obj {
			int i, dep, c;

			public Obj(int i, int dep, int c) {
				this.i = i;
				this.dep = dep;
				this.c = c;
			}
		}
	}

	static class SegTree<T> {
		// 親へのアクセス：(n - 1) / 2
		// 子へのアクセス：n * 2 + 1、n * 2 + 2
		int n = 2; // 要素（葉）の数
		int n2; // 全ノード数
		T NA;
		List<T> list;
		BiFunction<T, T, T> func;

		/**
		 * 初期化 O(N)
		 * @param num 要素（葉）の数
		 * @param na 無効とみなせる値
		 * @param func 区間に対する操作が可能な関数（戻り値は新規オブジェクト）
		 */
		public SegTree(int num, T na, BiFunction<T, T, T> func) {
			while (n < num) n <<= 1;
			n2 = n * 2 - 1;
			NA = na;
			list = new ArrayList<T>(n2);
			for (int i = 0; i < n2; i++) list.add(NA);
			this.func = func;
		}

		/**
		 * 更新 O(logN)
		 * @param i インデックス（0～n-1）
		 * @param x 更新値
		 */
		void update(int i, T x) {
			i += n - 1; // arr上でのインデックス
			list.set(i, x);
			while (i > 0) {
				i = (i - 1) / 2;
				list.set(i, func.apply(list.get(i * 2 + 1), list.get(i * 2 + 2)));
			}
		}

		/**
		 * 取得 O(logN)
		 * インデックスl以上r未満の区間の値
		 */
		T query(int l, int r) {
			return query(l, r, 0, 0, n);
		}

		/**
		 * 取得 O(logN)
		 * インデックスl以上r未満の区間の値、beg, endにはノードkに対応する区間
		 * query(l, r, 0, 0, n);
		 */
		private T query(int l, int r, int k, int beg, int end) {
			if (end <= l || r <= beg) return NA; // 交差しない
			if (l <= beg && end <= r) return list.get(k); // 完全に含む
			T v1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
			T v2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
			return func.apply(v1, v2);
		}
	}
}
0