oj.uz

Submission #697786

# Submission time Handle Problem Language Result Execution time Memory
697786 2023-02-11T05:07:32 Z vjudge1 Birthday gift (IZhO18_treearray) Java 11
30 / 100
 4000 ms 22116 KB 
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;

	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];
		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();
		}
		dfs(1, 1);
		outer:
		while (q-->0) {
			int t = scanner.nextInt();
			if (t == 1) {
				int pos = scanner.nextInt(), v = scanner.nextInt();
				a[pos] = v;
			} else {
				int l = scanner.nextInt(), r = scanner.nextInt(), v = scanner.nextInt();
				int curr = 0;
				for (int x = l; x <= r; x++) {
					for (int y = x; y <= r; y++) {
						if (y == x) curr = a[y];
						else curr = lca(curr, a[y]);
						if (curr == v) {
							out.println(x+" "+y);
							continue outer;
						}
					}
				}
				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;
	}
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10052 KB n=5
2 Correct 124 ms 11272 KB n=100
3 Correct 123 ms 12628 KB n=100
4 Correct 129 ms 13404 KB n=100
5 Correct 108 ms 10620 KB n=100
6 Correct 129 ms 10844 KB n=100
7 Correct 124 ms 10872 KB n=100
8 Correct 80 ms 9580 KB n=100
9 Correct 84 ms 10764 KB n=100
10 Correct 120 ms 10864 KB n=100
11 Correct 121 ms 10716 KB n=100
12 Correct 108 ms 10536 KB n=100
13 Correct 112 ms 10460 KB n=100
14 Correct 106 ms 10784 KB n=100
15 Correct 118 ms 10784 KB n=100
16 Correct 111 ms 10644 KB n=100
17 Correct 125 ms 11452 KB n=100
18 Correct 119 ms 11844 KB n=100
19 Correct 110 ms 10796 KB n=100
20 Correct 117 ms 11424 KB n=100
21 Correct 144 ms 13208 KB n=100
22 Correct 99 ms 9588 KB n=100
23 Correct 80 ms 10376 KB n=100
24 Correct 81 ms 10168 KB n=100
25 Correct 152 ms 13324 KB n=100
26 Correct 97 ms 9792 KB n=12
27 Correct 124 ms 11188 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10052 KB n=5
2 Correct 124 ms 11272 KB n=100
3 Correct 123 ms 12628 KB n=100
4 Correct 129 ms 13404 KB n=100
5 Correct 108 ms 10620 KB n=100
6 Correct 129 ms 10844 KB n=100
7 Correct 124 ms 10872 KB n=100
8 Correct 80 ms 9580 KB n=100
9 Correct 84 ms 10764 KB n=100
10 Correct 120 ms 10864 KB n=100
11 Correct 121 ms 10716 KB n=100
12 Correct 108 ms 10536 KB n=100
13 Correct 112 ms 10460 KB n=100
14 Correct 106 ms 10784 KB n=100
15 Correct 118 ms 10784 KB n=100
16 Correct 111 ms 10644 KB n=100
17 Correct 125 ms 11452 KB n=100
18 Correct 119 ms 11844 KB n=100
19 Correct 110 ms 10796 KB n=100
20 Correct 117 ms 11424 KB n=100
21 Correct 144 ms 13208 KB n=100
22 Correct 99 ms 9588 KB n=100
23 Correct 80 ms 10376 KB n=100
24 Correct 81 ms 10168 KB n=100
25 Correct 152 ms 13324 KB n=100
26 Correct 97 ms 9792 KB n=12
27 Correct 124 ms 11188 KB n=100
28 Correct 149 ms 11984 KB n=500
29 Correct 405 ms 12648 KB n=500
30 Correct 285 ms 12368 KB n=500
31 Correct 331 ms 12308 KB n=500
32 Correct 213 ms 18972 KB n=500
33 Correct 232 ms 12068 KB n=500
34 Correct 141 ms 12432 KB n=500
35 Correct 388 ms 12460 KB n=500
36 Correct 1387 ms 12176 KB n=500
37 Correct 1398 ms 12172 KB n=500
38 Correct 1381 ms 12196 KB n=500
39 Correct 247 ms 10860 KB n=500
40 Correct 243 ms 10860 KB n=500
41 Correct 234 ms 10852 KB n=500
42 Correct 760 ms 12280 KB n=500
43 Correct 805 ms 12184 KB n=500
44 Correct 774 ms 12264 KB n=500
45 Correct 298 ms 22116 KB n=500
46 Correct 340 ms 11796 KB n=500
47 Correct 290 ms 12140 KB n=500
48 Correct 128 ms 12252 KB n=500
49 Correct 341 ms 12216 KB n=500
50 Correct 237 ms 12256 KB n=500
51 Correct 396 ms 12236 KB n=500
52 Correct 449 ms 11696 KB n=500
53 Correct 385 ms 12160 KB n=500
54 Correct 295 ms 12452 KB n=500
55 Correct 145 ms 11308 KB n=278
56 Correct 1371 ms 10080 KB n=500
57 Correct 1389 ms 9944 KB n=500
58 Correct 716 ms 18768 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10052 KB n=5
2 Correct 124 ms 11272 KB n=100
3 Correct 123 ms 12628 KB n=100
4 Correct 129 ms 13404 KB n=100
5 Correct 108 ms 10620 KB n=100
6 Correct 129 ms 10844 KB n=100
7 Correct 124 ms 10872 KB n=100
8 Correct 80 ms 9580 KB n=100
9 Correct 84 ms 10764 KB n=100
10 Correct 120 ms 10864 KB n=100
11 Correct 121 ms 10716 KB n=100
12 Correct 108 ms 10536 KB n=100
13 Correct 112 ms 10460 KB n=100
14 Correct 106 ms 10784 KB n=100
15 Correct 118 ms 10784 KB n=100
16 Correct 111 ms 10644 KB n=100
17 Correct 125 ms 11452 KB n=100
18 Correct 119 ms 11844 KB n=100
19 Correct 110 ms 10796 KB n=100
20 Correct 117 ms 11424 KB n=100
21 Correct 144 ms 13208 KB n=100
22 Correct 99 ms 9588 KB n=100
23 Correct 80 ms 10376 KB n=100
24 Correct 81 ms 10168 KB n=100
25 Correct 152 ms 13324 KB n=100
26 Correct 97 ms 9792 KB n=12
27 Correct 124 ms 11188 KB n=100
28 Correct 149 ms 11984 KB n=500
29 Correct 405 ms 12648 KB n=500
30 Correct 285 ms 12368 KB n=500
31 Correct 331 ms 12308 KB n=500
32 Correct 213 ms 18972 KB n=500
33 Correct 232 ms 12068 KB n=500
34 Correct 141 ms 12432 KB n=500
35 Correct 388 ms 12460 KB n=500
36 Correct 1387 ms 12176 KB n=500
37 Correct 1398 ms 12172 KB n=500
38 Correct 1381 ms 12196 KB n=500
39 Correct 247 ms 10860 KB n=500
40 Correct 243 ms 10860 KB n=500
41 Correct 234 ms 10852 KB n=500
42 Correct 760 ms 12280 KB n=500
43 Correct 805 ms 12184 KB n=500
44 Correct 774 ms 12264 KB n=500
45 Correct 298 ms 22116 KB n=500
46 Correct 340 ms 11796 KB n=500
47 Correct 290 ms 12140 KB n=500
48 Correct 128 ms 12252 KB n=500
49 Correct 341 ms 12216 KB n=500
50 Correct 237 ms 12256 KB n=500
51 Correct 396 ms 12236 KB n=500
52 Correct 449 ms 11696 KB n=500
53 Correct 385 ms 12160 KB n=500
54 Correct 295 ms 12452 KB n=500
55 Correct 145 ms 11308 KB n=278
56 Correct 1371 ms 10080 KB n=500
57 Correct 1389 ms 9944 KB n=500
58 Correct 716 ms 18768 KB n=500
59 Correct 278 ms 13136 KB n=2000
60 Execution timed out 4050 ms 13728 KB Time limit exceeded
61 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 10052 KB n=5
2 Correct 124 ms 11272 KB n=100
3 Correct 123 ms 12628 KB n=100
4 Correct 129 ms 13404 KB n=100
5 Correct 108 ms 10620 KB n=100
6 Correct 129 ms 10844 KB n=100
7 Correct 124 ms 10872 KB n=100
8 Correct 80 ms 9580 KB n=100
9 Correct 84 ms 10764 KB n=100
10 Correct 120 ms 10864 KB n=100
11 Correct 121 ms 10716 KB n=100
12 Correct 108 ms 10536 KB n=100
13 Correct 112 ms 10460 KB n=100
14 Correct 106 ms 10784 KB n=100
15 Correct 118 ms 10784 KB n=100
16 Correct 111 ms 10644 KB n=100
17 Correct 125 ms 11452 KB n=100
18 Correct 119 ms 11844 KB n=100
19 Correct 110 ms 10796 KB n=100
20 Correct 117 ms 11424 KB n=100
21 Correct 144 ms 13208 KB n=100
22 Correct 99 ms 9588 KB n=100
23 Correct 80 ms 10376 KB n=100
24 Correct 81 ms 10168 KB n=100
25 Correct 152 ms 13324 KB n=100
26 Correct 97 ms 9792 KB n=12
27 Correct 124 ms 11188 KB n=100
28 Correct 149 ms 11984 KB n=500
29 Correct 405 ms 12648 KB n=500
30 Correct 285 ms 12368 KB n=500
31 Correct 331 ms 12308 KB n=500
32 Correct 213 ms 18972 KB n=500
33 Correct 232 ms 12068 KB n=500
34 Correct 141 ms 12432 KB n=500
35 Correct 388 ms 12460 KB n=500
36 Correct 1387 ms 12176 KB n=500
37 Correct 1398 ms 12172 KB n=500
38 Correct 1381 ms 12196 KB n=500
39 Correct 247 ms 10860 KB n=500
40 Correct 243 ms 10860 KB n=500
41 Correct 234 ms 10852 KB n=500
42 Correct 760 ms 12280 KB n=500
43 Correct 805 ms 12184 KB n=500
44 Correct 774 ms 12264 KB n=500
45 Correct 298 ms 22116 KB n=500
46 Correct 340 ms 11796 KB n=500
47 Correct 290 ms 12140 KB n=500
48 Correct 128 ms 12252 KB n=500
49 Correct 341 ms 12216 KB n=500
50 Correct 237 ms 12256 KB n=500
51 Correct 396 ms 12236 KB n=500
52 Correct 449 ms 11696 KB n=500
53 Correct 385 ms 12160 KB n=500
54 Correct 295 ms 12452 KB n=500
55 Correct 145 ms 11308 KB n=278
56 Correct 1371 ms 10080 KB n=500
57 Correct 1389 ms 9944 KB n=500
58 Correct 716 ms 18768 KB n=500
59 Correct 278 ms 13136 KB n=2000
60 Execution timed out 4050 ms 13728 KB Time limit exceeded
61 Halted 0 ms 0 KB -