oj.uz

Submission #719438

# Submission time Handle Problem Language Result Execution time Memory
719438 2023-04-05T22:41:34 Z Doncho_Bonboncho Birthday gift (IZhO18_treearray) C++14
100 / 100
 1067 ms 189032 KB 
#include <algorithm>
#include <bits/stdc++.h>
#include <iomanip>
#include <map>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

std::vector<int> v[MAX_N];
int a[MAX_N];
std::set<int> pos[MAX_N];
std::set<int> lcaPos[MAX_N];

int lca[MAX_N][30];
int dep[MAX_N];
bool viz[MAX_N];
void dfs( int x ){
	viz[x] = true;
	for( auto j : v[x] ){
		if( !viz[j] ){
			dep[j] = dep[x] +1;
			lca[j][0] = x;
			dfs(j);
		}
	}
}

int st;
int getLca( int a, int b ){
	if( dep[a] > dep[b] ) std::swap( a, b );
	int diff = dep[b] - dep[a];
	for( int i = st-1 ; i>=0 ; i-- ){
		if( (diff>>i)&1 ) b = lca[b][i];
	}
	if( a == b ) return a;
	for( int i=st-1 ; i>=0 ; i-- ){
		if( lca[a][i] != lca[b][i] ){
			a = lca[a][i];
			b = lca[b][i];
		}
	}
	return lca[a][0];
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n, m, q;
	std::cin>>n>>m>>q;
	for( int i=0 ; i<n-1 ; i++ ){
		int a, b;
		std::cin>>a>>b; a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	dfs(0);

	st = 0;
	while( true ){
		st ++;
		if( (1<<st) > n ) break;
		for( int i=0 ; i<n ; i++ ) lca[i][st] = lca[lca[i][st-1]][st-1];
	}

	for( int i=0 ; i<m ; i++ ){
		std::cin>>a[i]; a[i]--;
		pos[a[i]].insert(i);
		if( i ) lcaPos[ getLca(a[i-1], a[i]) ].insert(i-1);
	}

	while( q-- ){
		int t;
		std::cin>>t;
		if( t == 1 ){
			int p, v;
			std::cin>>p>>v; p--; v--;
			pos[a[p]].erase(p);
			pos[v].insert(p);
			if( p ){
				lcaPos[getLca( a[p-1], a[p] )].erase(p-1);
				lcaPos[getLca( a[p-1], v )].insert(p-1);
			}
			if( p < m-1 ){
				lcaPos[getLca( a[p], a[p+1] )].erase(p);
				lcaPos[getLca( v, a[p+1] )].insert(p);
			}
			a[p] = v;
		}else{
			int l, r, v;
			std::cin>>l>>r>>v;
			l--; r--; v--;
			
		//	std::cerr<<" ! "<<v<<"\n";
		//	for( auto j : pos[v] ) std::cerr<<j<<" ";
		//	std::cerr<<"\n\n";

			auto it = pos[v].lower_bound(l);
			if( it != pos[v].end() and *it <= r ){
				std::cout<<*it+1<<" "<<*it+1<<"\n";
				continue;
			}

			it = lcaPos[v].lower_bound(l);
			if( it != lcaPos[v].end() and *it <= r-1 ){
				std::cout<<*it+1<<" "<<*it+2<<"\n";
				continue;
			}
			std::cout<<"-1 -1\n";
		}
	}
	

	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117764 KB n=5
2 Correct 56 ms 117708 KB n=100
3 Correct 55 ms 117660 KB n=100
4 Correct 54 ms 117728 KB n=100
5 Correct 55 ms 117660 KB n=100
6 Correct 56 ms 117744 KB n=100
7 Correct 57 ms 117680 KB n=100
8 Correct 54 ms 117772 KB n=100
9 Correct 60 ms 117760 KB n=100
10 Correct 55 ms 117720 KB n=100
11 Correct 55 ms 117836 KB n=100
12 Correct 59 ms 117772 KB n=100
13 Correct 58 ms 117836 KB n=100
14 Correct 56 ms 117708 KB n=100
15 Correct 54 ms 117720 KB n=100
16 Correct 54 ms 117768 KB n=100
17 Correct 54 ms 117676 KB n=100
18 Correct 54 ms 117744 KB n=100
19 Correct 54 ms 117764 KB n=100
20 Correct 55 ms 117760 KB n=100
21 Correct 56 ms 117708 KB n=100
22 Correct 54 ms 117756 KB n=100
23 Correct 55 ms 117720 KB n=100
24 Correct 53 ms 117708 KB n=100
25 Correct 57 ms 117660 KB n=100
26 Correct 54 ms 117716 KB n=12
27 Correct 54 ms 117748 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117764 KB n=5
2 Correct 56 ms 117708 KB n=100
3 Correct 55 ms 117660 KB n=100
4 Correct 54 ms 117728 KB n=100
5 Correct 55 ms 117660 KB n=100
6 Correct 56 ms 117744 KB n=100
7 Correct 57 ms 117680 KB n=100
8 Correct 54 ms 117772 KB n=100
9 Correct 60 ms 117760 KB n=100
10 Correct 55 ms 117720 KB n=100
11 Correct 55 ms 117836 KB n=100
12 Correct 59 ms 117772 KB n=100
13 Correct 58 ms 117836 KB n=100
14 Correct 56 ms 117708 KB n=100
15 Correct 54 ms 117720 KB n=100
16 Correct 54 ms 117768 KB n=100
17 Correct 54 ms 117676 KB n=100
18 Correct 54 ms 117744 KB n=100
19 Correct 54 ms 117764 KB n=100
20 Correct 55 ms 117760 KB n=100
21 Correct 56 ms 117708 KB n=100
22 Correct 54 ms 117756 KB n=100
23 Correct 55 ms 117720 KB n=100
24 Correct 53 ms 117708 KB n=100
25 Correct 57 ms 117660 KB n=100
26 Correct 54 ms 117716 KB n=12
27 Correct 54 ms 117748 KB n=100
28 Correct 54 ms 117860 KB n=500
29 Correct 59 ms 117824 KB n=500
30 Correct 59 ms 117772 KB n=500
31 Correct 57 ms 117796 KB n=500
32 Correct 57 ms 117840 KB n=500
33 Correct 54 ms 117812 KB n=500
34 Correct 54 ms 117880 KB n=500
35 Correct 55 ms 117868 KB n=500
36 Correct 53 ms 117888 KB n=500
37 Correct 54 ms 117868 KB n=500
38 Correct 55 ms 117820 KB n=500
39 Correct 58 ms 117792 KB n=500
40 Correct 55 ms 117956 KB n=500
41 Correct 56 ms 117836 KB n=500
42 Correct 55 ms 117880 KB n=500
43 Correct 55 ms 117772 KB n=500
44 Correct 56 ms 117852 KB n=500
45 Correct 63 ms 117812 KB n=500
46 Correct 65 ms 117848 KB n=500
47 Correct 60 ms 117812 KB n=500
48 Correct 55 ms 117884 KB n=500
49 Correct 55 ms 117904 KB n=500
50 Correct 55 ms 117872 KB n=500
51 Correct 56 ms 117836 KB n=500
52 Correct 56 ms 117964 KB n=500
53 Correct 55 ms 117816 KB n=500
54 Correct 55 ms 117908 KB n=500
55 Correct 55 ms 117836 KB n=278
56 Correct 66 ms 117816 KB n=500
57 Correct 54 ms 117808 KB n=500
58 Correct 54 ms 117860 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117764 KB n=5
2 Correct 56 ms 117708 KB n=100
3 Correct 55 ms 117660 KB n=100
4 Correct 54 ms 117728 KB n=100
5 Correct 55 ms 117660 KB n=100
6 Correct 56 ms 117744 KB n=100
7 Correct 57 ms 117680 KB n=100
8 Correct 54 ms 117772 KB n=100
9 Correct 60 ms 117760 KB n=100
10 Correct 55 ms 117720 KB n=100
11 Correct 55 ms 117836 KB n=100
12 Correct 59 ms 117772 KB n=100
13 Correct 58 ms 117836 KB n=100
14 Correct 56 ms 117708 KB n=100
15 Correct 54 ms 117720 KB n=100
16 Correct 54 ms 117768 KB n=100
17 Correct 54 ms 117676 KB n=100
18 Correct 54 ms 117744 KB n=100
19 Correct 54 ms 117764 KB n=100
20 Correct 55 ms 117760 KB n=100
21 Correct 56 ms 117708 KB n=100
22 Correct 54 ms 117756 KB n=100
23 Correct 55 ms 117720 KB n=100
24 Correct 53 ms 117708 KB n=100
25 Correct 57 ms 117660 KB n=100
26 Correct 54 ms 117716 KB n=12
27 Correct 54 ms 117748 KB n=100
28 Correct 54 ms 117860 KB n=500
29 Correct 59 ms 117824 KB n=500
30 Correct 59 ms 117772 KB n=500
31 Correct 57 ms 117796 KB n=500
32 Correct 57 ms 117840 KB n=500
33 Correct 54 ms 117812 KB n=500
34 Correct 54 ms 117880 KB n=500
35 Correct 55 ms 117868 KB n=500
36 Correct 53 ms 117888 KB n=500
37 Correct 54 ms 117868 KB n=500
38 Correct 55 ms 117820 KB n=500
39 Correct 58 ms 117792 KB n=500
40 Correct 55 ms 117956 KB n=500
41 Correct 56 ms 117836 KB n=500
42 Correct 55 ms 117880 KB n=500
43 Correct 55 ms 117772 KB n=500
44 Correct 56 ms 117852 KB n=500
45 Correct 63 ms 117812 KB n=500
46 Correct 65 ms 117848 KB n=500
47 Correct 60 ms 117812 KB n=500
48 Correct 55 ms 117884 KB n=500
49 Correct 55 ms 117904 KB n=500
50 Correct 55 ms 117872 KB n=500
51 Correct 56 ms 117836 KB n=500
52 Correct 56 ms 117964 KB n=500
53 Correct 55 ms 117816 KB n=500
54 Correct 55 ms 117908 KB n=500
55 Correct 55 ms 117836 KB n=278
56 Correct 66 ms 117816 KB n=500
57 Correct 54 ms 117808 KB n=500
58 Correct 54 ms 117860 KB n=500
59 Correct 60 ms 118260 KB n=2000
60 Correct 58 ms 118384 KB n=2000
61 Correct 59 ms 118284 KB n=2000
62 Correct 61 ms 118336 KB n=2000
63 Correct 57 ms 118312 KB n=2000
64 Correct 58 ms 118344 KB n=2000
65 Correct 58 ms 118296 KB n=2000
66 Correct 60 ms 118396 KB n=2000
67 Correct 60 ms 118236 KB n=2000
68 Correct 59 ms 118336 KB n=2000
69 Correct 57 ms 118324 KB n=2000
70 Correct 61 ms 118220 KB n=2000
71 Correct 59 ms 118324 KB n=2000
72 Correct 59 ms 118228 KB n=2000
73 Correct 58 ms 118240 KB n=2000
74 Correct 57 ms 118280 KB n=1844
75 Correct 57 ms 118252 KB n=2000
76 Correct 60 ms 118232 KB n=2000
77 Correct 58 ms 118252 KB n=2000
78 Correct 60 ms 118260 KB n=2000
79 Correct 58 ms 118228 KB n=2000
80 Correct 58 ms 118372 KB n=2000
81 Correct 57 ms 118256 KB n=2000
82 Correct 59 ms 118220 KB n=2000
83 Correct 58 ms 118352 KB n=2000
84 Correct 58 ms 118256 KB n=2000
85 Correct 57 ms 118348 KB n=2000
86 Correct 58 ms 118220 KB n=2000
87 Correct 57 ms 118276 KB n=2000
88 Correct 58 ms 118348 KB n=2000
89 Correct 58 ms 118432 KB n=2000
90 Correct 57 ms 118324 KB n=2000
91 Correct 58 ms 118224 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 117764 KB n=5
2 Correct 56 ms 117708 KB n=100
3 Correct 55 ms 117660 KB n=100
4 Correct 54 ms 117728 KB n=100
5 Correct 55 ms 117660 KB n=100
6 Correct 56 ms 117744 KB n=100
7 Correct 57 ms 117680 KB n=100
8 Correct 54 ms 117772 KB n=100
9 Correct 60 ms 117760 KB n=100
10 Correct 55 ms 117720 KB n=100
11 Correct 55 ms 117836 KB n=100
12 Correct 59 ms 117772 KB n=100
13 Correct 58 ms 117836 KB n=100
14 Correct 56 ms 117708 KB n=100
15 Correct 54 ms 117720 KB n=100
16 Correct 54 ms 117768 KB n=100
17 Correct 54 ms 117676 KB n=100
18 Correct 54 ms 117744 KB n=100
19 Correct 54 ms 117764 KB n=100
20 Correct 55 ms 117760 KB n=100
21 Correct 56 ms 117708 KB n=100
22 Correct 54 ms 117756 KB n=100
23 Correct 55 ms 117720 KB n=100
24 Correct 53 ms 117708 KB n=100
25 Correct 57 ms 117660 KB n=100
26 Correct 54 ms 117716 KB n=12
27 Correct 54 ms 117748 KB n=100
28 Correct 54 ms 117860 KB n=500
29 Correct 59 ms 117824 KB n=500
30 Correct 59 ms 117772 KB n=500
31 Correct 57 ms 117796 KB n=500
32 Correct 57 ms 117840 KB n=500
33 Correct 54 ms 117812 KB n=500
34 Correct 54 ms 117880 KB n=500
35 Correct 55 ms 117868 KB n=500
36 Correct 53 ms 117888 KB n=500
37 Correct 54 ms 117868 KB n=500
38 Correct 55 ms 117820 KB n=500
39 Correct 58 ms 117792 KB n=500
40 Correct 55 ms 117956 KB n=500
41 Correct 56 ms 117836 KB n=500
42 Correct 55 ms 117880 KB n=500
43 Correct 55 ms 117772 KB n=500
44 Correct 56 ms 117852 KB n=500
45 Correct 63 ms 117812 KB n=500
46 Correct 65 ms 117848 KB n=500
47 Correct 60 ms 117812 KB n=500
48 Correct 55 ms 117884 KB n=500
49 Correct 55 ms 117904 KB n=500
50 Correct 55 ms 117872 KB n=500
51 Correct 56 ms 117836 KB n=500
52 Correct 56 ms 117964 KB n=500
53 Correct 55 ms 117816 KB n=500
54 Correct 55 ms 117908 KB n=500
55 Correct 55 ms 117836 KB n=278
56 Correct 66 ms 117816 KB n=500
57 Correct 54 ms 117808 KB n=500
58 Correct 54 ms 117860 KB n=500
59 Correct 60 ms 118260 KB n=2000
60 Correct 58 ms 118384 KB n=2000
61 Correct 59 ms 118284 KB n=2000
62 Correct 61 ms 118336 KB n=2000
63 Correct 57 ms 118312 KB n=2000
64 Correct 58 ms 118344 KB n=2000
65 Correct 58 ms 118296 KB n=2000
66 Correct 60 ms 118396 KB n=2000
67 Correct 60 ms 118236 KB n=2000
68 Correct 59 ms 118336 KB n=2000
69 Correct 57 ms 118324 KB n=2000
70 Correct 61 ms 118220 KB n=2000
71 Correct 59 ms 118324 KB n=2000
72 Correct 59 ms 118228 KB n=2000
73 Correct 58 ms 118240 KB n=2000
74 Correct 57 ms 118280 KB n=1844
75 Correct 57 ms 118252 KB n=2000
76 Correct 60 ms 118232 KB n=2000
77 Correct 58 ms 118252 KB n=2000
78 Correct 60 ms 118260 KB n=2000
79 Correct 58 ms 118228 KB n=2000
80 Correct 58 ms 118372 KB n=2000
81 Correct 57 ms 118256 KB n=2000
82 Correct 59 ms 118220 KB n=2000
83 Correct 58 ms 118352 KB n=2000
84 Correct 58 ms 118256 KB n=2000
85 Correct 57 ms 118348 KB n=2000
86 Correct 58 ms 118220 KB n=2000
87 Correct 57 ms 118276 KB n=2000
88 Correct 58 ms 118348 KB n=2000
89 Correct 58 ms 118432 KB n=2000
90 Correct 57 ms 118324 KB n=2000
91 Correct 58 ms 118224 KB n=2000
92 Correct 690 ms 176612 KB n=200000
93 Correct 1004 ms 182916 KB n=200000
94 Correct 925 ms 187644 KB n=200000
95 Correct 702 ms 176312 KB n=200000
96 Correct 682 ms 176368 KB n=200000
97 Correct 996 ms 181836 KB n=200000
98 Correct 706 ms 176192 KB n=200000
99 Correct 863 ms 176684 KB n=200000
100 Correct 704 ms 176520 KB n=200000
101 Correct 931 ms 189032 KB n=200000
102 Correct 472 ms 177524 KB n=200000
103 Correct 464 ms 177544 KB n=200000
104 Correct 474 ms 177520 KB n=200000
105 Correct 490 ms 177968 KB n=200000
106 Correct 471 ms 177868 KB n=200000
107 Correct 465 ms 177960 KB n=200000
108 Correct 793 ms 176364 KB n=200000
109 Correct 796 ms 176664 KB n=200000
110 Correct 776 ms 176384 KB n=200000
111 Correct 695 ms 175740 KB n=200000
112 Correct 928 ms 187816 KB n=200000
113 Correct 976 ms 181964 KB n=200000
114 Correct 808 ms 175872 KB n=200000
115 Correct 1067 ms 179020 KB n=200000
116 Correct 676 ms 176580 KB n=200000
117 Correct 882 ms 188496 KB n=200000
118 Correct 1020 ms 180264 KB n=200000
119 Correct 689 ms 176480 KB n=200000
120 Correct 865 ms 188168 KB n=200000
121 Correct 840 ms 188104 KB n=200000
122 Correct 886 ms 188576 KB n=200000
123 Correct 467 ms 177748 KB n=200000
124 Correct 243 ms 134008 KB n=25264