oj.uz

Submission #697809

# Submission time Handle Problem Language Result Execution time Memory
697809 2023-02-11T06:27:43 Z vjudge1 Birthday gift (IZhO18_treearray) Java 11
30 / 100
 4000 ms 21548 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 < 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);
		}
		tout[v] = ++timer;
	}
	
	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];
	}

	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 104 ms 9524 KB n=5
2 Correct 103 ms 9556 KB n=100
3 Correct 123 ms 9512 KB n=100
4 Correct 113 ms 9692 KB n=100
5 Correct 102 ms 9592 KB n=100
6 Correct 114 ms 10796 KB n=100
7 Correct 110 ms 10548 KB n=100
8 Correct 72 ms 9452 KB n=100
9 Correct 71 ms 9388 KB n=100
10 Correct 133 ms 10772 KB n=100
11 Correct 109 ms 10724 KB n=100
12 Correct 104 ms 9576 KB n=100
13 Correct 109 ms 9404 KB n=100
14 Correct 100 ms 9476 KB n=100
15 Correct 108 ms 9464 KB n=100
16 Correct 106 ms 9380 KB n=100
17 Correct 110 ms 10536 KB n=100
18 Correct 106 ms 10040 KB n=100
19 Correct 126 ms 9548 KB n=100
20 Correct 122 ms 10596 KB n=100
21 Correct 136 ms 10696 KB n=100
22 Correct 100 ms 9288 KB n=100
23 Correct 89 ms 10632 KB n=100
24 Correct 86 ms 10564 KB n=100
25 Correct 143 ms 13428 KB n=100
26 Correct 95 ms 9620 KB n=12
27 Correct 121 ms 9520 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9524 KB n=5
2 Correct 103 ms 9556 KB n=100
3 Correct 123 ms 9512 KB n=100
4 Correct 113 ms 9692 KB n=100
5 Correct 102 ms 9592 KB n=100
6 Correct 114 ms 10796 KB n=100
7 Correct 110 ms 10548 KB n=100
8 Correct 72 ms 9452 KB n=100
9 Correct 71 ms 9388 KB n=100
10 Correct 133 ms 10772 KB n=100
11 Correct 109 ms 10724 KB n=100
12 Correct 104 ms 9576 KB n=100
13 Correct 109 ms 9404 KB n=100
14 Correct 100 ms 9476 KB n=100
15 Correct 108 ms 9464 KB n=100
16 Correct 106 ms 9380 KB n=100
17 Correct 110 ms 10536 KB n=100
18 Correct 106 ms 10040 KB n=100
19 Correct 126 ms 9548 KB n=100
20 Correct 122 ms 10596 KB n=100
21 Correct 136 ms 10696 KB n=100
22 Correct 100 ms 9288 KB n=100
23 Correct 89 ms 10632 KB n=100
24 Correct 86 ms 10564 KB n=100
25 Correct 143 ms 13428 KB n=100
26 Correct 95 ms 9620 KB n=12
27 Correct 121 ms 9520 KB n=100
28 Correct 145 ms 12500 KB n=500
29 Correct 216 ms 19372 KB n=500
30 Correct 176 ms 13072 KB n=500
31 Correct 200 ms 13180 KB n=500
32 Correct 149 ms 12216 KB n=500
33 Correct 169 ms 12456 KB n=500
34 Correct 148 ms 12576 KB n=500
35 Correct 328 ms 21500 KB n=500
36 Correct 217 ms 16928 KB n=500
37 Correct 219 ms 16680 KB n=500
38 Correct 199 ms 17236 KB n=500
39 Correct 163 ms 15208 KB n=500
40 Correct 169 ms 15160 KB n=500
41 Correct 161 ms 15080 KB n=500
42 Correct 254 ms 19800 KB n=500
43 Correct 229 ms 19292 KB n=500
44 Correct 250 ms 19288 KB n=500
45 Correct 156 ms 12724 KB n=500
46 Correct 242 ms 15708 KB n=500
47 Correct 248 ms 19560 KB n=500
48 Correct 134 ms 12356 KB n=500
49 Correct 261 ms 21548 KB n=500
50 Correct 212 ms 19340 KB n=500
51 Correct 240 ms 19936 KB n=500
52 Correct 162 ms 13140 KB n=500
53 Correct 255 ms 19884 KB n=500
54 Correct 263 ms 12940 KB n=500
55 Correct 146 ms 11328 KB n=278
56 Correct 1814 ms 10236 KB n=500
57 Correct 1855 ms 10540 KB n=500
58 Correct 250 ms 18320 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9524 KB n=5
2 Correct 103 ms 9556 KB n=100
3 Correct 123 ms 9512 KB n=100
4 Correct 113 ms 9692 KB n=100
5 Correct 102 ms 9592 KB n=100
6 Correct 114 ms 10796 KB n=100
7 Correct 110 ms 10548 KB n=100
8 Correct 72 ms 9452 KB n=100
9 Correct 71 ms 9388 KB n=100
10 Correct 133 ms 10772 KB n=100
11 Correct 109 ms 10724 KB n=100
12 Correct 104 ms 9576 KB n=100
13 Correct 109 ms 9404 KB n=100
14 Correct 100 ms 9476 KB n=100
15 Correct 108 ms 9464 KB n=100
16 Correct 106 ms 9380 KB n=100
17 Correct 110 ms 10536 KB n=100
18 Correct 106 ms 10040 KB n=100
19 Correct 126 ms 9548 KB n=100
20 Correct 122 ms 10596 KB n=100
21 Correct 136 ms 10696 KB n=100
22 Correct 100 ms 9288 KB n=100
23 Correct 89 ms 10632 KB n=100
24 Correct 86 ms 10564 KB n=100
25 Correct 143 ms 13428 KB n=100
26 Correct 95 ms 9620 KB n=12
27 Correct 121 ms 9520 KB n=100
28 Correct 145 ms 12500 KB n=500
29 Correct 216 ms 19372 KB n=500
30 Correct 176 ms 13072 KB n=500
31 Correct 200 ms 13180 KB n=500
32 Correct 149 ms 12216 KB n=500
33 Correct 169 ms 12456 KB n=500
34 Correct 148 ms 12576 KB n=500
35 Correct 328 ms 21500 KB n=500
36 Correct 217 ms 16928 KB n=500
37 Correct 219 ms 16680 KB n=500
38 Correct 199 ms 17236 KB n=500
39 Correct 163 ms 15208 KB n=500
40 Correct 169 ms 15160 KB n=500
41 Correct 161 ms 15080 KB n=500
42 Correct 254 ms 19800 KB n=500
43 Correct 229 ms 19292 KB n=500
44 Correct 250 ms 19288 KB n=500
45 Correct 156 ms 12724 KB n=500
46 Correct 242 ms 15708 KB n=500
47 Correct 248 ms 19560 KB n=500
48 Correct 134 ms 12356 KB n=500
49 Correct 261 ms 21548 KB n=500
50 Correct 212 ms 19340 KB n=500
51 Correct 240 ms 19936 KB n=500
52 Correct 162 ms 13140 KB n=500
53 Correct 255 ms 19884 KB n=500
54 Correct 263 ms 12940 KB n=500
55 Correct 146 ms 11328 KB n=278
56 Correct 1814 ms 10236 KB n=500
57 Correct 1855 ms 10540 KB n=500
58 Correct 250 ms 18320 KB n=500
59 Correct 224 ms 13388 KB n=2000
60 Correct 437 ms 13692 KB n=2000
61 Correct 352 ms 13444 KB n=2000
62 Correct 330 ms 13676 KB n=2000
63 Correct 206 ms 13392 KB n=2000
64 Correct 341 ms 13408 KB n=2000
65 Correct 206 ms 13436 KB n=2000
66 Correct 369 ms 13420 KB n=2000
67 Correct 217 ms 13556 KB n=2000
68 Correct 364 ms 13424 KB n=2000
69 Correct 331 ms 13556 KB n=2000
70 Correct 346 ms 13536 KB n=2000
71 Correct 324 ms 13588 KB n=2000
72 Correct 244 ms 12500 KB n=2000
73 Correct 224 ms 12156 KB n=2000
74 Correct 203 ms 13576 KB n=1844
75 Correct 236 ms 12316 KB n=2000
76 Correct 273 ms 13576 KB n=2000
77 Correct 285 ms 13748 KB n=2000
78 Correct 269 ms 13320 KB n=2000
79 Correct 200 ms 13428 KB n=2000
80 Correct 308 ms 13780 KB n=2000
81 Correct 327 ms 13436 KB n=2000
82 Correct 198 ms 13372 KB n=2000
83 Correct 322 ms 14084 KB n=2000
84 Correct 222 ms 13328 KB n=2000
85 Correct 443 ms 13304 KB n=2000
86 Correct 277 ms 14416 KB n=2000
87 Correct 244 ms 14828 KB n=2000
88 Execution timed out 4064 ms 12424 KB Time limit exceeded
89 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9524 KB n=5
2 Correct 103 ms 9556 KB n=100
3 Correct 123 ms 9512 KB n=100
4 Correct 113 ms 9692 KB n=100
5 Correct 102 ms 9592 KB n=100
6 Correct 114 ms 10796 KB n=100
7 Correct 110 ms 10548 KB n=100
8 Correct 72 ms 9452 KB n=100
9 Correct 71 ms 9388 KB n=100
10 Correct 133 ms 10772 KB n=100
11 Correct 109 ms 10724 KB n=100
12 Correct 104 ms 9576 KB n=100
13 Correct 109 ms 9404 KB n=100
14 Correct 100 ms 9476 KB n=100
15 Correct 108 ms 9464 KB n=100
16 Correct 106 ms 9380 KB n=100
17 Correct 110 ms 10536 KB n=100
18 Correct 106 ms 10040 KB n=100
19 Correct 126 ms 9548 KB n=100
20 Correct 122 ms 10596 KB n=100
21 Correct 136 ms 10696 KB n=100
22 Correct 100 ms 9288 KB n=100
23 Correct 89 ms 10632 KB n=100
24 Correct 86 ms 10564 KB n=100
25 Correct 143 ms 13428 KB n=100
26 Correct 95 ms 9620 KB n=12
27 Correct 121 ms 9520 KB n=100
28 Correct 145 ms 12500 KB n=500
29 Correct 216 ms 19372 KB n=500
30 Correct 176 ms 13072 KB n=500
31 Correct 200 ms 13180 KB n=500
32 Correct 149 ms 12216 KB n=500
33 Correct 169 ms 12456 KB n=500
34 Correct 148 ms 12576 KB n=500
35 Correct 328 ms 21500 KB n=500
36 Correct 217 ms 16928 KB n=500
37 Correct 219 ms 16680 KB n=500
38 Correct 199 ms 17236 KB n=500
39 Correct 163 ms 15208 KB n=500
40 Correct 169 ms 15160 KB n=500
41 Correct 161 ms 15080 KB n=500
42 Correct 254 ms 19800 KB n=500
43 Correct 229 ms 19292 KB n=500
44 Correct 250 ms 19288 KB n=500
45 Correct 156 ms 12724 KB n=500
46 Correct 242 ms 15708 KB n=500
47 Correct 248 ms 19560 KB n=500
48 Correct 134 ms 12356 KB n=500
49 Correct 261 ms 21548 KB n=500
50 Correct 212 ms 19340 KB n=500
51 Correct 240 ms 19936 KB n=500
52 Correct 162 ms 13140 KB n=500
53 Correct 255 ms 19884 KB n=500
54 Correct 263 ms 12940 KB n=500
55 Correct 146 ms 11328 KB n=278
56 Correct 1814 ms 10236 KB n=500
57 Correct 1855 ms 10540 KB n=500
58 Correct 250 ms 18320 KB n=500
59 Correct 224 ms 13388 KB n=2000
60 Correct 437 ms 13692 KB n=2000
61 Correct 352 ms 13444 KB n=2000
62 Correct 330 ms 13676 KB n=2000
63 Correct 206 ms 13392 KB n=2000
64 Correct 341 ms 13408 KB n=2000
65 Correct 206 ms 13436 KB n=2000
66 Correct 369 ms 13420 KB n=2000
67 Correct 217 ms 13556 KB n=2000
68 Correct 364 ms 13424 KB n=2000
69 Correct 331 ms 13556 KB n=2000
70 Correct 346 ms 13536 KB n=2000
71 Correct 324 ms 13588 KB n=2000
72 Correct 244 ms 12500 KB n=2000
73 Correct 224 ms 12156 KB n=2000
74 Correct 203 ms 13576 KB n=1844
75 Correct 236 ms 12316 KB n=2000
76 Correct 273 ms 13576 KB n=2000
77 Correct 285 ms 13748 KB n=2000
78 Correct 269 ms 13320 KB n=2000
79 Correct 200 ms 13428 KB n=2000
80 Correct 308 ms 13780 KB n=2000
81 Correct 327 ms 13436 KB n=2000
82 Correct 198 ms 13372 KB n=2000
83 Correct 322 ms 14084 KB n=2000
84 Correct 222 ms 13328 KB n=2000
85 Correct 443 ms 13304 KB n=2000
86 Correct 277 ms 14416 KB n=2000
87 Correct 244 ms 14828 KB n=2000
88 Execution timed out 4064 ms 12424 KB Time limit exceeded
89 Halted 0 ms 0 KB -