oj.uz

Submission #697862

# Submission time Handle Problem Language Result Execution time Memory
697862 2023-02-11T08:54:29 Z vjudge1 Birthday gift (IZhO18_treearray) Java 11
56 / 100
 2984 ms 262144 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 = Integer.MAX_VALUE;
	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;
	}
}

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 163 ms 11756 KB n=5
2 Correct 158 ms 11928 KB n=100
3 Correct 156 ms 11576 KB n=100
4 Correct 174 ms 11928 KB n=100
5 Correct 157 ms 11900 KB n=100
6 Correct 114 ms 10328 KB n=100
7 Correct 115 ms 10492 KB n=100
8 Correct 64 ms 8436 KB n=100
9 Correct 62 ms 8428 KB n=100
10 Correct 122 ms 10784 KB n=100
11 Correct 134 ms 10748 KB n=100
12 Correct 162 ms 11860 KB n=100
13 Correct 159 ms 12216 KB n=100
14 Correct 155 ms 11704 KB n=100
15 Correct 170 ms 11768 KB n=100
16 Correct 162 ms 11784 KB n=100
17 Correct 113 ms 10520 KB n=100
18 Correct 116 ms 10556 KB n=100
19 Correct 162 ms 11932 KB n=100
20 Correct 148 ms 11868 KB n=100
21 Correct 120 ms 10520 KB n=100
22 Correct 159 ms 11996 KB n=100
23 Correct 66 ms 8484 KB n=100
24 Correct 67 ms 8260 KB n=100
25 Correct 129 ms 10348 KB n=100
26 Correct 146 ms 11928 KB n=12
27 Correct 113 ms 10432 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11756 KB n=5
2 Correct 158 ms 11928 KB n=100
3 Correct 156 ms 11576 KB n=100
4 Correct 174 ms 11928 KB n=100
5 Correct 157 ms 11900 KB n=100
6 Correct 114 ms 10328 KB n=100
7 Correct 115 ms 10492 KB n=100
8 Correct 64 ms 8436 KB n=100
9 Correct 62 ms 8428 KB n=100
10 Correct 122 ms 10784 KB n=100
11 Correct 134 ms 10748 KB n=100
12 Correct 162 ms 11860 KB n=100
13 Correct 159 ms 12216 KB n=100
14 Correct 155 ms 11704 KB n=100
15 Correct 170 ms 11768 KB n=100
16 Correct 162 ms 11784 KB n=100
17 Correct 113 ms 10520 KB n=100
18 Correct 116 ms 10556 KB n=100
19 Correct 162 ms 11932 KB n=100
20 Correct 148 ms 11868 KB n=100
21 Correct 120 ms 10520 KB n=100
22 Correct 159 ms 11996 KB n=100
23 Correct 66 ms 8484 KB n=100
24 Correct 67 ms 8260 KB n=100
25 Correct 129 ms 10348 KB n=100
26 Correct 146 ms 11928 KB n=12
27 Correct 113 ms 10432 KB n=100
28 Correct 237 ms 13048 KB n=500
29 Correct 141 ms 11484 KB n=500
30 Correct 215 ms 13032 KB n=500
31 Correct 211 ms 13124 KB n=500
32 Correct 216 ms 13132 KB n=500
33 Correct 204 ms 13260 KB n=500
34 Correct 257 ms 13072 KB n=500
35 Correct 201 ms 12708 KB n=500
36 Correct 173 ms 12524 KB n=500
37 Correct 203 ms 12392 KB n=500
38 Correct 175 ms 12792 KB n=500
39 Correct 119 ms 11004 KB n=500
40 Correct 116 ms 11044 KB n=500
41 Correct 124 ms 11128 KB n=500
42 Correct 188 ms 12656 KB n=500
43 Correct 196 ms 12660 KB n=500
44 Correct 194 ms 12800 KB n=500
45 Correct 228 ms 13232 KB n=500
46 Correct 160 ms 11588 KB n=500
47 Correct 201 ms 13116 KB n=500
48 Correct 212 ms 13408 KB n=500
49 Correct 208 ms 13100 KB n=500
50 Correct 188 ms 12784 KB n=500
51 Correct 203 ms 13364 KB n=500
52 Correct 175 ms 11372 KB n=500
53 Correct 217 ms 13020 KB n=500
54 Correct 179 ms 12620 KB n=500
55 Correct 197 ms 11908 KB n=278
56 Correct 89 ms 9264 KB n=500
57 Correct 94 ms 10108 KB n=500
58 Correct 167 ms 12364 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11756 KB n=5
2 Correct 158 ms 11928 KB n=100
3 Correct 156 ms 11576 KB n=100
4 Correct 174 ms 11928 KB n=100
5 Correct 157 ms 11900 KB n=100
6 Correct 114 ms 10328 KB n=100
7 Correct 115 ms 10492 KB n=100
8 Correct 64 ms 8436 KB n=100
9 Correct 62 ms 8428 KB n=100
10 Correct 122 ms 10784 KB n=100
11 Correct 134 ms 10748 KB n=100
12 Correct 162 ms 11860 KB n=100
13 Correct 159 ms 12216 KB n=100
14 Correct 155 ms 11704 KB n=100
15 Correct 170 ms 11768 KB n=100
16 Correct 162 ms 11784 KB n=100
17 Correct 113 ms 10520 KB n=100
18 Correct 116 ms 10556 KB n=100
19 Correct 162 ms 11932 KB n=100
20 Correct 148 ms 11868 KB n=100
21 Correct 120 ms 10520 KB n=100
22 Correct 159 ms 11996 KB n=100
23 Correct 66 ms 8484 KB n=100
24 Correct 67 ms 8260 KB n=100
25 Correct 129 ms 10348 KB n=100
26 Correct 146 ms 11928 KB n=12
27 Correct 113 ms 10432 KB n=100
28 Correct 237 ms 13048 KB n=500
29 Correct 141 ms 11484 KB n=500
30 Correct 215 ms 13032 KB n=500
31 Correct 211 ms 13124 KB n=500
32 Correct 216 ms 13132 KB n=500
33 Correct 204 ms 13260 KB n=500
34 Correct 257 ms 13072 KB n=500
35 Correct 201 ms 12708 KB n=500
36 Correct 173 ms 12524 KB n=500
37 Correct 203 ms 12392 KB n=500
38 Correct 175 ms 12792 KB n=500
39 Correct 119 ms 11004 KB n=500
40 Correct 116 ms 11044 KB n=500
41 Correct 124 ms 11128 KB n=500
42 Correct 188 ms 12656 KB n=500
43 Correct 196 ms 12660 KB n=500
44 Correct 194 ms 12800 KB n=500
45 Correct 228 ms 13232 KB n=500
46 Correct 160 ms 11588 KB n=500
47 Correct 201 ms 13116 KB n=500
48 Correct 212 ms 13408 KB n=500
49 Correct 208 ms 13100 KB n=500
50 Correct 188 ms 12784 KB n=500
51 Correct 203 ms 13364 KB n=500
52 Correct 175 ms 11372 KB n=500
53 Correct 217 ms 13020 KB n=500
54 Correct 179 ms 12620 KB n=500
55 Correct 197 ms 11908 KB n=278
56 Correct 89 ms 9264 KB n=500
57 Correct 94 ms 10108 KB n=500
58 Correct 167 ms 12364 KB n=500
59 Correct 388 ms 15860 KB n=2000
60 Correct 372 ms 16412 KB n=2000
61 Correct 346 ms 15940 KB n=2000
62 Correct 326 ms 15920 KB n=2000
63 Correct 365 ms 16008 KB n=2000
64 Correct 324 ms 16064 KB n=2000
65 Correct 302 ms 15728 KB n=2000
66 Correct 344 ms 15996 KB n=2000
67 Correct 354 ms 15928 KB n=2000
68 Correct 350 ms 15812 KB n=2000
69 Correct 321 ms 16060 KB n=2000
70 Correct 363 ms 15840 KB n=2000
71 Correct 314 ms 15960 KB n=2000
72 Correct 206 ms 12884 KB n=2000
73 Correct 209 ms 12916 KB n=2000
74 Correct 348 ms 15968 KB n=1844
75 Correct 215 ms 12816 KB n=2000
76 Correct 318 ms 15956 KB n=2000
77 Correct 311 ms 15920 KB n=2000
78 Correct 348 ms 15936 KB n=2000
79 Correct 374 ms 15700 KB n=2000
80 Correct 344 ms 16020 KB n=2000
81 Correct 322 ms 16112 KB n=2000
82 Correct 352 ms 15928 KB n=2000
83 Correct 333 ms 15972 KB n=2000
84 Correct 299 ms 15856 KB n=2000
85 Correct 309 ms 15876 KB n=2000
86 Correct 313 ms 16080 KB n=2000
87 Correct 345 ms 15784 KB n=2000
88 Correct 237 ms 13256 KB n=2000
89 Correct 233 ms 14208 KB n=2000
90 Correct 319 ms 15964 KB n=2000
91 Correct 283 ms 15996 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11756 KB n=5
2 Correct 158 ms 11928 KB n=100
3 Correct 156 ms 11576 KB n=100
4 Correct 174 ms 11928 KB n=100
5 Correct 157 ms 11900 KB n=100
6 Correct 114 ms 10328 KB n=100
7 Correct 115 ms 10492 KB n=100
8 Correct 64 ms 8436 KB n=100
9 Correct 62 ms 8428 KB n=100
10 Correct 122 ms 10784 KB n=100
11 Correct 134 ms 10748 KB n=100
12 Correct 162 ms 11860 KB n=100
13 Correct 159 ms 12216 KB n=100
14 Correct 155 ms 11704 KB n=100
15 Correct 170 ms 11768 KB n=100
16 Correct 162 ms 11784 KB n=100
17 Correct 113 ms 10520 KB n=100
18 Correct 116 ms 10556 KB n=100
19 Correct 162 ms 11932 KB n=100
20 Correct 148 ms 11868 KB n=100
21 Correct 120 ms 10520 KB n=100
22 Correct 159 ms 11996 KB n=100
23 Correct 66 ms 8484 KB n=100
24 Correct 67 ms 8260 KB n=100
25 Correct 129 ms 10348 KB n=100
26 Correct 146 ms 11928 KB n=12
27 Correct 113 ms 10432 KB n=100
28 Correct 237 ms 13048 KB n=500
29 Correct 141 ms 11484 KB n=500
30 Correct 215 ms 13032 KB n=500
31 Correct 211 ms 13124 KB n=500
32 Correct 216 ms 13132 KB n=500
33 Correct 204 ms 13260 KB n=500
34 Correct 257 ms 13072 KB n=500
35 Correct 201 ms 12708 KB n=500
36 Correct 173 ms 12524 KB n=500
37 Correct 203 ms 12392 KB n=500
38 Correct 175 ms 12792 KB n=500
39 Correct 119 ms 11004 KB n=500
40 Correct 116 ms 11044 KB n=500
41 Correct 124 ms 11128 KB n=500
42 Correct 188 ms 12656 KB n=500
43 Correct 196 ms 12660 KB n=500
44 Correct 194 ms 12800 KB n=500
45 Correct 228 ms 13232 KB n=500
46 Correct 160 ms 11588 KB n=500
47 Correct 201 ms 13116 KB n=500
48 Correct 212 ms 13408 KB n=500
49 Correct 208 ms 13100 KB n=500
50 Correct 188 ms 12784 KB n=500
51 Correct 203 ms 13364 KB n=500
52 Correct 175 ms 11372 KB n=500
53 Correct 217 ms 13020 KB n=500
54 Correct 179 ms 12620 KB n=500
55 Correct 197 ms 11908 KB n=278
56 Correct 89 ms 9264 KB n=500
57 Correct 94 ms 10108 KB n=500
58 Correct 167 ms 12364 KB n=500
59 Correct 388 ms 15860 KB n=2000
60 Correct 372 ms 16412 KB n=2000
61 Correct 346 ms 15940 KB n=2000
62 Correct 326 ms 15920 KB n=2000
63 Correct 365 ms 16008 KB n=2000
64 Correct 324 ms 16064 KB n=2000
65 Correct 302 ms 15728 KB n=2000
66 Correct 344 ms 15996 KB n=2000
67 Correct 354 ms 15928 KB n=2000
68 Correct 350 ms 15812 KB n=2000
69 Correct 321 ms 16060 KB n=2000
70 Correct 363 ms 15840 KB n=2000
71 Correct 314 ms 15960 KB n=2000
72 Correct 206 ms 12884 KB n=2000
73 Correct 209 ms 12916 KB n=2000
74 Correct 348 ms 15968 KB n=1844
75 Correct 215 ms 12816 KB n=2000
76 Correct 318 ms 15956 KB n=2000
77 Correct 311 ms 15920 KB n=2000
78 Correct 348 ms 15936 KB n=2000
79 Correct 374 ms 15700 KB n=2000
80 Correct 344 ms 16020 KB n=2000
81 Correct 322 ms 16112 KB n=2000
82 Correct 352 ms 15928 KB n=2000
83 Correct 333 ms 15972 KB n=2000
84 Correct 299 ms 15856 KB n=2000
85 Correct 309 ms 15876 KB n=2000
86 Correct 313 ms 16080 KB n=2000
87 Correct 345 ms 15784 KB n=2000
88 Correct 237 ms 13256 KB n=2000
89 Correct 233 ms 14208 KB n=2000
90 Correct 319 ms 15964 KB n=2000
91 Correct 283 ms 15996 KB n=2000
92 Correct 2377 ms 182216 KB n=200000
93 Correct 2726 ms 186452 KB n=200000
94 Correct 2734 ms 187356 KB n=200000
95 Correct 2103 ms 176816 KB n=200000
96 Correct 2129 ms 178884 KB n=200000
97 Correct 2689 ms 186176 KB n=200000
98 Correct 2290 ms 175772 KB n=200000
99 Correct 2488 ms 181392 KB n=200000
100 Correct 2045 ms 175564 KB n=200000
101 Correct 2984 ms 190256 KB n=200000
102 Correct 1516 ms 174440 KB n=200000
103 Correct 1488 ms 175420 KB n=200000
104 Correct 1577 ms 175380 KB n=200000
105 Correct 1512 ms 175500 KB n=200000
106 Correct 1529 ms 175684 KB n=200000
107 Correct 1535 ms 176200 KB n=200000
108 Correct 2226 ms 176852 KB n=200000
109 Correct 2201 ms 179524 KB n=200000
110 Correct 2345 ms 178044 KB n=200000
111 Correct 2047 ms 173032 KB n=200000
112 Correct 2817 ms 191036 KB n=200000
113 Correct 2636 ms 183804 KB n=200000
114 Correct 2149 ms 176944 KB n=200000
115 Correct 2792 ms 184068 KB n=200000
116 Correct 2106 ms 174252 KB n=200000
117 Correct 2805 ms 190768 KB n=200000
118 Correct 2855 ms 185480 KB n=200000
119 Correct 2137 ms 174760 KB n=200000
120 Runtime error 1124 ms 262144 KB Execution killed with signal 9
121 Halted 0 ms 0 KB -