oj.uz

Submission #697812

# Submission time Handle Problem Language Result Execution time Memory
697812 2023-02-11T06:30:50 Z vjudge1 Birthday gift (IZhO18_treearray) Java 11
30 / 100
 4000 ms 21652 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, timer;
	int[] a, d, tin, tout;
	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]; tin = new int[n+1]; tout = 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;
						}
						if (!isPar(v, curr)) break;
					}
				}
				out.println("-1 -1");
			}
		}
	}

	void dfs(int v, int pr){
		tin[v] = ++timer;
		up[0][v] = pr;
		for(int i = 1; i < 13; 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);
		}
		tout[v] = ++timer;
	}
	
	int lca(int u, int v){
		if(d[u] < d[v]) {
			int temp = u;
			u = v;
			v = temp;
		}
		for(int i = 12; i >= 0; i--){
			if(d[u] - (1<<i) >= d[v]) {
				u = up[i][u];
			}
		}
		if(u == v) return u;
		for(int i = 12; i >= 0; i--){
			if(up[i][u] != up[i][v]) {
				u = up[i][u];
				v = up[i][v];
			}
		}
		return up[0][v];
	}

	boolean isPar(int a, int b) {		
		return tin[a] <= tin[b] && tout[a] >= tout[b];
	}

	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 95 ms 9612 KB n=5
2 Correct 99 ms 9476 KB n=100
3 Correct 96 ms 9508 KB n=100
4 Correct 98 ms 9580 KB n=100
5 Correct 96 ms 9624 KB n=100
6 Correct 107 ms 10776 KB n=100
7 Correct 115 ms 10680 KB n=100
8 Correct 69 ms 9916 KB n=100
9 Correct 68 ms 9476 KB n=100
10 Correct 111 ms 10612 KB n=100
11 Correct 106 ms 10828 KB n=100
12 Correct 99 ms 9600 KB n=100
13 Correct 101 ms 9620 KB n=100
14 Correct 101 ms 9376 KB n=100
15 Correct 98 ms 9576 KB n=100
16 Correct 98 ms 9704 KB n=100
17 Correct 109 ms 10644 KB n=100
18 Correct 111 ms 10328 KB n=100
19 Correct 97 ms 9628 KB n=100
20 Correct 111 ms 10736 KB n=100
21 Correct 112 ms 10868 KB n=100
22 Correct 96 ms 9684 KB n=100
23 Correct 88 ms 10792 KB n=100
24 Correct 84 ms 10632 KB n=100
25 Correct 146 ms 13392 KB n=100
26 Correct 95 ms 9728 KB n=12
27 Correct 99 ms 9540 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9612 KB n=5
2 Correct 99 ms 9476 KB n=100
3 Correct 96 ms 9508 KB n=100
4 Correct 98 ms 9580 KB n=100
5 Correct 96 ms 9624 KB n=100
6 Correct 107 ms 10776 KB n=100
7 Correct 115 ms 10680 KB n=100
8 Correct 69 ms 9916 KB n=100
9 Correct 68 ms 9476 KB n=100
10 Correct 111 ms 10612 KB n=100
11 Correct 106 ms 10828 KB n=100
12 Correct 99 ms 9600 KB n=100
13 Correct 101 ms 9620 KB n=100
14 Correct 101 ms 9376 KB n=100
15 Correct 98 ms 9576 KB n=100
16 Correct 98 ms 9704 KB n=100
17 Correct 109 ms 10644 KB n=100
18 Correct 111 ms 10328 KB n=100
19 Correct 97 ms 9628 KB n=100
20 Correct 111 ms 10736 KB n=100
21 Correct 112 ms 10868 KB n=100
22 Correct 96 ms 9684 KB n=100
23 Correct 88 ms 10792 KB n=100
24 Correct 84 ms 10632 KB n=100
25 Correct 146 ms 13392 KB n=100
26 Correct 95 ms 9728 KB n=12
27 Correct 99 ms 9540 KB n=100
28 Correct 114 ms 9804 KB n=500
29 Correct 205 ms 19568 KB n=500
30 Correct 154 ms 13120 KB n=500
31 Correct 166 ms 13268 KB n=500
32 Correct 117 ms 9916 KB n=500
33 Correct 141 ms 11488 KB n=500
34 Correct 118 ms 11192 KB n=500
35 Correct 282 ms 21652 KB n=500
36 Correct 193 ms 17088 KB n=500
37 Correct 176 ms 17032 KB n=500
38 Correct 191 ms 16908 KB n=500
39 Correct 138 ms 15272 KB n=500
40 Correct 137 ms 15316 KB n=500
41 Correct 133 ms 15104 KB n=500
42 Correct 222 ms 19708 KB n=500
43 Correct 199 ms 19304 KB n=500
44 Correct 209 ms 19256 KB n=500
45 Correct 119 ms 11164 KB n=500
46 Correct 179 ms 15712 KB n=500
47 Correct 208 ms 19768 KB n=500
48 Correct 112 ms 9864 KB n=500
49 Correct 215 ms 21336 KB n=500
50 Correct 181 ms 19244 KB n=500
51 Correct 207 ms 19860 KB n=500
52 Correct 169 ms 13012 KB n=500
53 Correct 205 ms 19748 KB n=500
54 Correct 220 ms 11832 KB n=500
55 Correct 136 ms 11568 KB n=278
56 Correct 1052 ms 10144 KB n=500
57 Correct 1042 ms 10360 KB n=500
58 Correct 219 ms 18536 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9612 KB n=5
2 Correct 99 ms 9476 KB n=100
3 Correct 96 ms 9508 KB n=100
4 Correct 98 ms 9580 KB n=100
5 Correct 96 ms 9624 KB n=100
6 Correct 107 ms 10776 KB n=100
7 Correct 115 ms 10680 KB n=100
8 Correct 69 ms 9916 KB n=100
9 Correct 68 ms 9476 KB n=100
10 Correct 111 ms 10612 KB n=100
11 Correct 106 ms 10828 KB n=100
12 Correct 99 ms 9600 KB n=100
13 Correct 101 ms 9620 KB n=100
14 Correct 101 ms 9376 KB n=100
15 Correct 98 ms 9576 KB n=100
16 Correct 98 ms 9704 KB n=100
17 Correct 109 ms 10644 KB n=100
18 Correct 111 ms 10328 KB n=100
19 Correct 97 ms 9628 KB n=100
20 Correct 111 ms 10736 KB n=100
21 Correct 112 ms 10868 KB n=100
22 Correct 96 ms 9684 KB n=100
23 Correct 88 ms 10792 KB n=100
24 Correct 84 ms 10632 KB n=100
25 Correct 146 ms 13392 KB n=100
26 Correct 95 ms 9728 KB n=12
27 Correct 99 ms 9540 KB n=100
28 Correct 114 ms 9804 KB n=500
29 Correct 205 ms 19568 KB n=500
30 Correct 154 ms 13120 KB n=500
31 Correct 166 ms 13268 KB n=500
32 Correct 117 ms 9916 KB n=500
33 Correct 141 ms 11488 KB n=500
34 Correct 118 ms 11192 KB n=500
35 Correct 282 ms 21652 KB n=500
36 Correct 193 ms 17088 KB n=500
37 Correct 176 ms 17032 KB n=500
38 Correct 191 ms 16908 KB n=500
39 Correct 138 ms 15272 KB n=500
40 Correct 137 ms 15316 KB n=500
41 Correct 133 ms 15104 KB n=500
42 Correct 222 ms 19708 KB n=500
43 Correct 199 ms 19304 KB n=500
44 Correct 209 ms 19256 KB n=500
45 Correct 119 ms 11164 KB n=500
46 Correct 179 ms 15712 KB n=500
47 Correct 208 ms 19768 KB n=500
48 Correct 112 ms 9864 KB n=500
49 Correct 215 ms 21336 KB n=500
50 Correct 181 ms 19244 KB n=500
51 Correct 207 ms 19860 KB n=500
52 Correct 169 ms 13012 KB n=500
53 Correct 205 ms 19748 KB n=500
54 Correct 220 ms 11832 KB n=500
55 Correct 136 ms 11568 KB n=278
56 Correct 1052 ms 10144 KB n=500
57 Correct 1042 ms 10360 KB n=500
58 Correct 219 ms 18536 KB n=500
59 Correct 208 ms 13384 KB n=2000
60 Correct 366 ms 13852 KB n=2000
61 Correct 324 ms 13484 KB n=2000
62 Correct 318 ms 13440 KB n=2000
63 Correct 227 ms 13372 KB n=2000
64 Correct 344 ms 13732 KB n=2000
65 Correct 199 ms 13756 KB n=2000
66 Correct 398 ms 13540 KB n=2000
67 Correct 226 ms 13448 KB n=2000
68 Correct 329 ms 13560 KB n=2000
69 Correct 320 ms 13268 KB n=2000
70 Correct 315 ms 13404 KB n=2000
71 Correct 308 ms 13452 KB n=2000
72 Correct 225 ms 12272 KB n=2000
73 Correct 213 ms 12204 KB n=2000
74 Correct 201 ms 13588 KB n=1844
75 Correct 214 ms 12152 KB n=2000
76 Correct 278 ms 13232 KB n=2000
77 Correct 270 ms 13216 KB n=2000
78 Correct 280 ms 13384 KB n=2000
79 Correct 206 ms 13384 KB n=2000
80 Correct 300 ms 13512 KB n=2000
81 Correct 311 ms 13364 KB n=2000
82 Correct 219 ms 13364 KB n=2000
83 Correct 352 ms 14124 KB n=2000
84 Correct 227 ms 13356 KB n=2000
85 Correct 412 ms 13256 KB n=2000
86 Correct 312 ms 14140 KB n=2000
87 Correct 246 ms 14488 KB n=2000
88 Execution timed out 4082 ms 12072 KB Time limit exceeded
89 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 9612 KB n=5
2 Correct 99 ms 9476 KB n=100
3 Correct 96 ms 9508 KB n=100
4 Correct 98 ms 9580 KB n=100
5 Correct 96 ms 9624 KB n=100
6 Correct 107 ms 10776 KB n=100
7 Correct 115 ms 10680 KB n=100
8 Correct 69 ms 9916 KB n=100
9 Correct 68 ms 9476 KB n=100
10 Correct 111 ms 10612 KB n=100
11 Correct 106 ms 10828 KB n=100
12 Correct 99 ms 9600 KB n=100
13 Correct 101 ms 9620 KB n=100
14 Correct 101 ms 9376 KB n=100
15 Correct 98 ms 9576 KB n=100
16 Correct 98 ms 9704 KB n=100
17 Correct 109 ms 10644 KB n=100
18 Correct 111 ms 10328 KB n=100
19 Correct 97 ms 9628 KB n=100
20 Correct 111 ms 10736 KB n=100
21 Correct 112 ms 10868 KB n=100
22 Correct 96 ms 9684 KB n=100
23 Correct 88 ms 10792 KB n=100
24 Correct 84 ms 10632 KB n=100
25 Correct 146 ms 13392 KB n=100
26 Correct 95 ms 9728 KB n=12
27 Correct 99 ms 9540 KB n=100
28 Correct 114 ms 9804 KB n=500
29 Correct 205 ms 19568 KB n=500
30 Correct 154 ms 13120 KB n=500
31 Correct 166 ms 13268 KB n=500
32 Correct 117 ms 9916 KB n=500
33 Correct 141 ms 11488 KB n=500
34 Correct 118 ms 11192 KB n=500
35 Correct 282 ms 21652 KB n=500
36 Correct 193 ms 17088 KB n=500
37 Correct 176 ms 17032 KB n=500
38 Correct 191 ms 16908 KB n=500
39 Correct 138 ms 15272 KB n=500
40 Correct 137 ms 15316 KB n=500
41 Correct 133 ms 15104 KB n=500
42 Correct 222 ms 19708 KB n=500
43 Correct 199 ms 19304 KB n=500
44 Correct 209 ms 19256 KB n=500
45 Correct 119 ms 11164 KB n=500
46 Correct 179 ms 15712 KB n=500
47 Correct 208 ms 19768 KB n=500
48 Correct 112 ms 9864 KB n=500
49 Correct 215 ms 21336 KB n=500
50 Correct 181 ms 19244 KB n=500
51 Correct 207 ms 19860 KB n=500
52 Correct 169 ms 13012 KB n=500
53 Correct 205 ms 19748 KB n=500
54 Correct 220 ms 11832 KB n=500
55 Correct 136 ms 11568 KB n=278
56 Correct 1052 ms 10144 KB n=500
57 Correct 1042 ms 10360 KB n=500
58 Correct 219 ms 18536 KB n=500
59 Correct 208 ms 13384 KB n=2000
60 Correct 366 ms 13852 KB n=2000
61 Correct 324 ms 13484 KB n=2000
62 Correct 318 ms 13440 KB n=2000
63 Correct 227 ms 13372 KB n=2000
64 Correct 344 ms 13732 KB n=2000
65 Correct 199 ms 13756 KB n=2000
66 Correct 398 ms 13540 KB n=2000
67 Correct 226 ms 13448 KB n=2000
68 Correct 329 ms 13560 KB n=2000
69 Correct 320 ms 13268 KB n=2000
70 Correct 315 ms 13404 KB n=2000
71 Correct 308 ms 13452 KB n=2000
72 Correct 225 ms 12272 KB n=2000
73 Correct 213 ms 12204 KB n=2000
74 Correct 201 ms 13588 KB n=1844
75 Correct 214 ms 12152 KB n=2000
76 Correct 278 ms 13232 KB n=2000
77 Correct 270 ms 13216 KB n=2000
78 Correct 280 ms 13384 KB n=2000
79 Correct 206 ms 13384 KB n=2000
80 Correct 300 ms 13512 KB n=2000
81 Correct 311 ms 13364 KB n=2000
82 Correct 219 ms 13364 KB n=2000
83 Correct 352 ms 14124 KB n=2000
84 Correct 227 ms 13356 KB n=2000
85 Correct 412 ms 13256 KB n=2000
86 Correct 312 ms 14140 KB n=2000
87 Correct 246 ms 14488 KB n=2000
88 Execution timed out 4082 ms 12072 KB Time limit exceeded
89 Halted 0 ms 0 KB -