제출 #697844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697844		vjudge1	Birthday gift (IZhO18_treearray)	Java	56 / 100	2927 ms	262144 KiB

treearray

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.IntStream;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.stream.IntStream.*;

/********************************************/
public class treearray {
	public static void main(String[] args) throws IOException {
		new Solution().run();
	}
}
/********************************************/

class Solution {
	final FastScanner scanner = new FastScanner();
	final PrintWriter out = new PrintWriter(System.out);
	final int mod = (int) 1e9+7;
	final int[] dx = {1, 0, -1, 0};
	final int[] dy = {0, 1, 0, -1};
	int maxn = (int) 3e5+10;
	int n, m, q;
	int[] a, d;
	int[][] up;
	TreeSet<Integer>[] s, t;

	void solve() throws IOException {
		n = scanner.nextInt(); m = scanner.nextInt(); q = scanner.nextInt();
		init(n); up = new int[20][n+1]; a = new int[m+1]; d = new int[n+1];
		s = new TreeSet[n+1]; t = new TreeSet[n+1];
		for (int i = 1; i<n; i++) {
			int x = scanner.nextInt(), y = scanner.nextInt();
			g[x].add(y); g[y].add(x);
		}
		for (int i = 1; i<=m; i++) {
			a[i] = scanner.nextInt();
		}
		for (int i = 1; i<=n; i++) {
			s[i] = new TreeSet<>();
			t[i] = new TreeSet<>();
		}
		dfs(1, 1);
		for (int i = 1; i<=m; i++) s[a[i]].add(i);
		for (int i = 2; i<=m; i++) t[lca(a[i], a[i-1])].add(i);
		for(int i = 1; i <= n; i++) {
			s[i].add(mod);
			t[i].add(mod);
		}
		for(int i = 0, type, l, r, x; i < q; i++){
			type = scanner.nextInt();
			if (type == 1){
				l = scanner.nextInt(); x = scanner.nextInt();
				s[a[l]].remove(l);
				if(l > 1) t[lca(a[l], a[l-1])].remove(l);
				if(l < m) t[lca(a[l], a[l+1])].remove(l+1);
				a[l] = x;
				s[a[l]].add(l);
				if(l > 1) t[lca(a[l], a[l-1])].add(l);
				if(l < m) t[lca(a[l], a[l+1])].add(l+1);
			} else { 
				l = scanner.nextInt(); r = scanner.nextInt(); x = scanner.nextInt();
				var d = s[x].ceiling(l);
				var e = t[x].ceiling(l+1);
				if (d!=null && d <= r){
					out.println(d+" "+d);
				} else if(e!=null && e <= r){
					out.println((e-1)+" "+e);
				} else{
					out.println("-1 -1");
				}
			}
		}
	}

	void dfs(int v, int pr) {
		up[0][v] = pr;
		for(int i = 1; i < 19; i++){
			up[i][v] = up[i-1][up[i-1][v]];
		}
		d[v] = d[pr] + 1;
		for(var to : g[v]) {
			if(to == pr) continue;
			dfs(to, v);
		}
	}
	
	int lca(int u, int v) {
		if(d[u] < d[v]) {
			int temp = u;
			u = v;
			v = temp;
		}
		for(int i = 18; i >= 0; i--){
			if(d[u] - (1<<i) >= d[v]) {
				u = up[i][u];
			}
		}
		if(u == v) return u;
		for(int i = 18; i >= 0; i--){
			if(up[i][u] != up[i][v]) {
				u = up[i][u];
				v = up[i][v];
			}
		}
		return up[0][v];
	}

	List<Integer>[] g;
	boolean[] was;

	void init(int n) {
		g = new ArrayList[n+1];
		was = new boolean[n+1];
		for (int i = 0; i<=n; i++) {
			g[i] = new ArrayList<>();
		}
	}

	void run() throws IOException {
		int t = 1;
		while (t-->0) {
			solve();
		}
		out.flush();
	}
}

class FastScanner {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	int nextInt() throws IOException {
		int x = 0, sign = 1;
		char c = (char) br.read();
		
		while ((c < '0' || c > '9') && c != '-') {
			c = (char) br.read();
		}
		if (c == '-') {
			sign = -1;
			c = (char) br.read();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 3) + (x << 1) + (c & 15);
			c = (char) br.read();
		}
		return sign * x;
	}
	
	long nextLong() throws IOException {
		long x = 0, sign = 1;
		char c = (char) br.read();
		
		while ((c < '0' || c > '9') && c != '-') {
			c = (char) br.read();
		}
		if (c == '-') {
			sign = -1;
			c = (char) br.read();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 3) + (x << 1) + (c & 15);
			c = (char) br.read();
		}
		return sign * x;
	}
	
	String next() throws IOException {
		StringBuilder sb = new StringBuilder();
		char c = (char) br.read();
		while (c == ' ' || c == '\n' || c == '\r') {
			c = (char) br.read();
		}
		while (c != ' ' && c != '\n' && c != '\r') {
			sb.append(c);
			c = (char) br.read();
		}
		return sb.toString();
	}
	
	int[] readArray(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) a[i] = nextInt();
		return a;
	}
	
	long[] readLong(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++) a[i] = nextInt();
		return a;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Note: treearray.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44