結果
問題 | No.1030 だんしんぐぱーりない |
ユーザー | ks2m |
提出日時 | 2020-04-17 22:50:41 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,856 ms / 2,000 ms |
コード長 | 5,501 bytes |
コンパイル時間 | 4,547 ms |
コンパイル使用メモリ | 84,536 KB |
実行使用メモリ | 95,672 KB |
最終ジャッジ日時 | 2023-07-27 01:45:10 |
合計ジャッジ時間 | 51,768 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 52 ms
50,232 KB |
testcase_01 | AC | 51 ms
49,844 KB |
testcase_02 | AC | 53 ms
50,348 KB |
testcase_03 | AC | 51 ms
50,064 KB |
testcase_04 | AC | 52 ms
50,156 KB |
testcase_05 | AC | 1,382 ms
79,492 KB |
testcase_06 | AC | 1,285 ms
78,528 KB |
testcase_07 | AC | 1,013 ms
68,108 KB |
testcase_08 | AC | 984 ms
67,444 KB |
testcase_09 | AC | 1,316 ms
79,592 KB |
testcase_10 | AC | 760 ms
63,528 KB |
testcase_11 | AC | 1,285 ms
69,820 KB |
testcase_12 | AC | 1,227 ms
78,516 KB |
testcase_13 | AC | 1,156 ms
80,944 KB |
testcase_14 | AC | 1,389 ms
75,540 KB |
testcase_15 | AC | 962 ms
66,508 KB |
testcase_16 | AC | 1,252 ms
71,760 KB |
testcase_17 | AC | 1,335 ms
81,076 KB |
testcase_18 | AC | 1,455 ms
74,008 KB |
testcase_19 | AC | 1,035 ms
66,960 KB |
testcase_20 | AC | 1,162 ms
71,728 KB |
testcase_21 | AC | 1,089 ms
70,848 KB |
testcase_22 | AC | 1,134 ms
71,736 KB |
testcase_23 | AC | 1,324 ms
72,808 KB |
testcase_24 | AC | 1,098 ms
68,292 KB |
testcase_25 | AC | 1,182 ms
66,360 KB |
testcase_26 | AC | 924 ms
61,960 KB |
testcase_27 | AC | 1,037 ms
66,420 KB |
testcase_28 | AC | 1,295 ms
77,400 KB |
testcase_29 | AC | 1,112 ms
77,196 KB |
testcase_30 | AC | 1,064 ms
71,808 KB |
testcase_31 | AC | 1,132 ms
68,672 KB |
testcase_32 | AC | 1,343 ms
80,056 KB |
testcase_33 | AC | 1,305 ms
78,572 KB |
testcase_34 | AC | 828 ms
66,436 KB |
testcase_35 | AC | 1,762 ms
91,056 KB |
testcase_36 | AC | 1,790 ms
93,356 KB |
testcase_37 | AC | 1,770 ms
95,332 KB |
testcase_38 | AC | 1,856 ms
94,724 KB |
testcase_39 | AC | 1,772 ms
95,672 KB |
testcase_40 | AC | 54 ms
49,868 KB |
testcase_41 | AC | 51 ms
49,940 KB |
ソースコード
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); } } }