oj.uz

Submission #1100574

# Submission time Handle Problem Language Result Execution time Memory
1100574 2024-10-14T09:14:12 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
100 / 100
 791 ms 141048 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int N = 500001;

using namespace std;

ll n, m, k, a, b, c, e, d[N], bg[N], p[N], sz[N], h[N], up[N][22], tin[N], lc, sum, sum1, ans, mx[N], tout[N];
set <ll> s[N], st[N];
vector <ll> g[N];

void dfs (ll v, ll pp){
	up[v][0] = pp;
	sz[v] = 1;
	for (int i = 1; i <= 21; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i] != pp){
			d[g[v][i]] = d[v] + 1;
			dfs (g[v][i], v);
		}
	}
}

ll lca (ll a, ll b){
	if (d[a] < d[b]){
		swap (a, b);
	}
	ll c = abs (d[a] - d[b]);
	for (int i = 21; i >= 0; i--){
		if ((c >> i) & 1){
			a = up[a][i];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = 21; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb (a);
	}
	for (int i = 1; i <= m; i++){
		cin >> p[i];
	}
	dfs (1, 0);
	for (int i = 1; i < m; i++){
		st[p[i]].insert (i);
		s[lca (p[i], p[i + 1])].insert (i);
	}
	st[p[m]].insert(m);
	while (k--){
		cin >> a >> b >> c;
		if (a == 1){
			st[p[b]].erase (b);
			if (b != 1)s[lca (p[b], p[b - 1])].erase (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].erase (b);
			p[b] = c;
			st[p[b]].insert(b);
			if (b != 1)s[lca (p[b], p[b - 1])].insert (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].insert (b);
		}
		else{
			cin >> e;
			if (s[e].size() && *s[e].lower_bound(b) < c && *s[e].lower_bound(b) >= b){
				lc = *s[e].lower_bound(b);
				cout << lc << ' ' << lc + 1 << '\n';
			}
			else if (st[e].size() && *st[e].lower_bound(b) <= c && *st[e].lower_bound(b) >= b){
				cout << *st[e].lower_bound(b) << ' ' << *st[e].lower_bound (b) << '\n';
			}
			else{
				cout << "-1 -1\n";
			}
		}
	}
}

Compilation message

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 68176 KB n=5
2 Correct 12 ms 68360 KB n=100
3 Correct 12 ms 68176 KB n=100
4 Correct 11 ms 68176 KB n=100
5 Correct 10 ms 68176 KB n=100
6 Correct 10 ms 68464 KB n=100
7 Correct 10 ms 68176 KB n=100
8 Correct 10 ms 66300 KB n=100
9 Correct 10 ms 66128 KB n=100
10 Correct 10 ms 68192 KB n=100
11 Correct 10 ms 68176 KB n=100
12 Correct 11 ms 68176 KB n=100
13 Correct 11 ms 68176 KB n=100
14 Correct 10 ms 68176 KB n=100
15 Correct 10 ms 68176 KB n=100
16 Correct 10 ms 68176 KB n=100
17 Correct 10 ms 68176 KB n=100
18 Correct 11 ms 68176 KB n=100
19 Correct 10 ms 68344 KB n=100
20 Correct 10 ms 68176 KB n=100
21 Correct 12 ms 68176 KB n=100
22 Correct 10 ms 68176 KB n=100
23 Correct 11 ms 66128 KB n=100
24 Correct 10 ms 66128 KB n=100
25 Correct 10 ms 68176 KB n=100
26 Correct 12 ms 68372 KB n=12
27 Correct 10 ms 68176 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 68176 KB n=5
2 Correct 12 ms 68360 KB n=100
3 Correct 12 ms 68176 KB n=100
4 Correct 11 ms 68176 KB n=100
5 Correct 10 ms 68176 KB n=100
6 Correct 10 ms 68464 KB n=100
7 Correct 10 ms 68176 KB n=100
8 Correct 10 ms 66300 KB n=100
9 Correct 10 ms 66128 KB n=100
10 Correct 10 ms 68192 KB n=100
11 Correct 10 ms 68176 KB n=100
12 Correct 11 ms 68176 KB n=100
13 Correct 11 ms 68176 KB n=100
14 Correct 10 ms 68176 KB n=100
15 Correct 10 ms 68176 KB n=100
16 Correct 10 ms 68176 KB n=100
17 Correct 10 ms 68176 KB n=100
18 Correct 11 ms 68176 KB n=100
19 Correct 10 ms 68344 KB n=100
20 Correct 10 ms 68176 KB n=100
21 Correct 12 ms 68176 KB n=100
22 Correct 10 ms 68176 KB n=100
23 Correct 11 ms 66128 KB n=100
24 Correct 10 ms 66128 KB n=100
25 Correct 10 ms 68176 KB n=100
26 Correct 12 ms 68372 KB n=12
27 Correct 10 ms 68176 KB n=100
28 Correct 12 ms 68432 KB n=500
29 Correct 13 ms 68432 KB n=500
30 Correct 15 ms 68432 KB n=500
31 Correct 13 ms 68432 KB n=500
32 Correct 12 ms 68432 KB n=500
33 Correct 13 ms 68432 KB n=500
34 Correct 12 ms 68324 KB n=500
35 Correct 12 ms 68432 KB n=500
36 Correct 12 ms 68432 KB n=500
37 Correct 12 ms 68436 KB n=500
38 Correct 11 ms 68432 KB n=500
39 Correct 12 ms 66384 KB n=500
40 Correct 12 ms 66384 KB n=500
41 Correct 13 ms 66256 KB n=500
42 Correct 13 ms 68432 KB n=500
43 Correct 12 ms 68436 KB n=500
44 Correct 12 ms 68604 KB n=500
45 Correct 12 ms 68312 KB n=500
46 Correct 12 ms 68432 KB n=500
47 Correct 12 ms 68432 KB n=500
48 Correct 13 ms 68432 KB n=500
49 Correct 14 ms 68444 KB n=500
50 Correct 13 ms 66396 KB n=500
51 Correct 12 ms 68432 KB n=500
52 Correct 13 ms 68432 KB n=500
53 Correct 13 ms 68432 KB n=500
54 Correct 12 ms 68432 KB n=500
55 Correct 11 ms 68176 KB n=278
56 Correct 12 ms 66384 KB n=500
57 Correct 11 ms 66384 KB n=500
58 Correct 15 ms 68432 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 68176 KB n=5
2 Correct 12 ms 68360 KB n=100
3 Correct 12 ms 68176 KB n=100
4 Correct 11 ms 68176 KB n=100
5 Correct 10 ms 68176 KB n=100
6 Correct 10 ms 68464 KB n=100
7 Correct 10 ms 68176 KB n=100
8 Correct 10 ms 66300 KB n=100
9 Correct 10 ms 66128 KB n=100
10 Correct 10 ms 68192 KB n=100
11 Correct 10 ms 68176 KB n=100
12 Correct 11 ms 68176 KB n=100
13 Correct 11 ms 68176 KB n=100
14 Correct 10 ms 68176 KB n=100
15 Correct 10 ms 68176 KB n=100
16 Correct 10 ms 68176 KB n=100
17 Correct 10 ms 68176 KB n=100
18 Correct 11 ms 68176 KB n=100
19 Correct 10 ms 68344 KB n=100
20 Correct 10 ms 68176 KB n=100
21 Correct 12 ms 68176 KB n=100
22 Correct 10 ms 68176 KB n=100
23 Correct 11 ms 66128 KB n=100
24 Correct 10 ms 66128 KB n=100
25 Correct 10 ms 68176 KB n=100
26 Correct 12 ms 68372 KB n=12
27 Correct 10 ms 68176 KB n=100
28 Correct 12 ms 68432 KB n=500
29 Correct 13 ms 68432 KB n=500
30 Correct 15 ms 68432 KB n=500
31 Correct 13 ms 68432 KB n=500
32 Correct 12 ms 68432 KB n=500
33 Correct 13 ms 68432 KB n=500
34 Correct 12 ms 68324 KB n=500
35 Correct 12 ms 68432 KB n=500
36 Correct 12 ms 68432 KB n=500
37 Correct 12 ms 68436 KB n=500
38 Correct 11 ms 68432 KB n=500
39 Correct 12 ms 66384 KB n=500
40 Correct 12 ms 66384 KB n=500
41 Correct 13 ms 66256 KB n=500
42 Correct 13 ms 68432 KB n=500
43 Correct 12 ms 68436 KB n=500
44 Correct 12 ms 68604 KB n=500
45 Correct 12 ms 68312 KB n=500
46 Correct 12 ms 68432 KB n=500
47 Correct 12 ms 68432 KB n=500
48 Correct 13 ms 68432 KB n=500
49 Correct 14 ms 68444 KB n=500
50 Correct 13 ms 66396 KB n=500
51 Correct 12 ms 68432 KB n=500
52 Correct 13 ms 68432 KB n=500
53 Correct 13 ms 68432 KB n=500
54 Correct 12 ms 68432 KB n=500
55 Correct 11 ms 68176 KB n=278
56 Correct 12 ms 66384 KB n=500
57 Correct 11 ms 66384 KB n=500
58 Correct 15 ms 68432 KB n=500
59 Correct 14 ms 68432 KB n=2000
60 Correct 14 ms 68688 KB n=2000
61 Correct 15 ms 68688 KB n=2000
62 Correct 15 ms 68432 KB n=2000
63 Correct 14 ms 68432 KB n=2000
64 Correct 14 ms 68688 KB n=2000
65 Correct 14 ms 68432 KB n=2000
66 Correct 14 ms 68688 KB n=2000
67 Correct 15 ms 68536 KB n=2000
68 Correct 14 ms 68688 KB n=2000
69 Correct 15 ms 68432 KB n=2000
70 Correct 14 ms 68432 KB n=2000
71 Correct 14 ms 68432 KB n=2000
72 Correct 18 ms 66384 KB n=2000
73 Correct 13 ms 66384 KB n=2000
74 Correct 15 ms 68432 KB n=1844
75 Correct 13 ms 66552 KB n=2000
76 Correct 15 ms 68432 KB n=2000
77 Correct 15 ms 68432 KB n=2000
78 Correct 15 ms 68432 KB n=2000
79 Correct 14 ms 68432 KB n=2000
80 Correct 13 ms 68688 KB n=2000
81 Correct 15 ms 68436 KB n=2000
82 Correct 15 ms 68444 KB n=2000
83 Correct 15 ms 68700 KB n=2000
84 Correct 14 ms 68600 KB n=2000
85 Correct 14 ms 68444 KB n=2000
86 Correct 15 ms 68432 KB n=2000
87 Correct 15 ms 68432 KB n=2000
88 Correct 14 ms 66640 KB n=2000
89 Correct 14 ms 66640 KB n=2000
90 Correct 14 ms 68732 KB n=2000
91 Correct 14 ms 68432 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 68176 KB n=5
2 Correct 12 ms 68360 KB n=100
3 Correct 12 ms 68176 KB n=100
4 Correct 11 ms 68176 KB n=100
5 Correct 10 ms 68176 KB n=100
6 Correct 10 ms 68464 KB n=100
7 Correct 10 ms 68176 KB n=100
8 Correct 10 ms 66300 KB n=100
9 Correct 10 ms 66128 KB n=100
10 Correct 10 ms 68192 KB n=100
11 Correct 10 ms 68176 KB n=100
12 Correct 11 ms 68176 KB n=100
13 Correct 11 ms 68176 KB n=100
14 Correct 10 ms 68176 KB n=100
15 Correct 10 ms 68176 KB n=100
16 Correct 10 ms 68176 KB n=100
17 Correct 10 ms 68176 KB n=100
18 Correct 11 ms 68176 KB n=100
19 Correct 10 ms 68344 KB n=100
20 Correct 10 ms 68176 KB n=100
21 Correct 12 ms 68176 KB n=100
22 Correct 10 ms 68176 KB n=100
23 Correct 11 ms 66128 KB n=100
24 Correct 10 ms 66128 KB n=100
25 Correct 10 ms 68176 KB n=100
26 Correct 12 ms 68372 KB n=12
27 Correct 10 ms 68176 KB n=100
28 Correct 12 ms 68432 KB n=500
29 Correct 13 ms 68432 KB n=500
30 Correct 15 ms 68432 KB n=500
31 Correct 13 ms 68432 KB n=500
32 Correct 12 ms 68432 KB n=500
33 Correct 13 ms 68432 KB n=500
34 Correct 12 ms 68324 KB n=500
35 Correct 12 ms 68432 KB n=500
36 Correct 12 ms 68432 KB n=500
37 Correct 12 ms 68436 KB n=500
38 Correct 11 ms 68432 KB n=500
39 Correct 12 ms 66384 KB n=500
40 Correct 12 ms 66384 KB n=500
41 Correct 13 ms 66256 KB n=500
42 Correct 13 ms 68432 KB n=500
43 Correct 12 ms 68436 KB n=500
44 Correct 12 ms 68604 KB n=500
45 Correct 12 ms 68312 KB n=500
46 Correct 12 ms 68432 KB n=500
47 Correct 12 ms 68432 KB n=500
48 Correct 13 ms 68432 KB n=500
49 Correct 14 ms 68444 KB n=500
50 Correct 13 ms 66396 KB n=500
51 Correct 12 ms 68432 KB n=500
52 Correct 13 ms 68432 KB n=500
53 Correct 13 ms 68432 KB n=500
54 Correct 12 ms 68432 KB n=500
55 Correct 11 ms 68176 KB n=278
56 Correct 12 ms 66384 KB n=500
57 Correct 11 ms 66384 KB n=500
58 Correct 15 ms 68432 KB n=500
59 Correct 14 ms 68432 KB n=2000
60 Correct 14 ms 68688 KB n=2000
61 Correct 15 ms 68688 KB n=2000
62 Correct 15 ms 68432 KB n=2000
63 Correct 14 ms 68432 KB n=2000
64 Correct 14 ms 68688 KB n=2000
65 Correct 14 ms 68432 KB n=2000
66 Correct 14 ms 68688 KB n=2000
67 Correct 15 ms 68536 KB n=2000
68 Correct 14 ms 68688 KB n=2000
69 Correct 15 ms 68432 KB n=2000
70 Correct 14 ms 68432 KB n=2000
71 Correct 14 ms 68432 KB n=2000
72 Correct 18 ms 66384 KB n=2000
73 Correct 13 ms 66384 KB n=2000
74 Correct 15 ms 68432 KB n=1844
75 Correct 13 ms 66552 KB n=2000
76 Correct 15 ms 68432 KB n=2000
77 Correct 15 ms 68432 KB n=2000
78 Correct 15 ms 68432 KB n=2000
79 Correct 14 ms 68432 KB n=2000
80 Correct 13 ms 68688 KB n=2000
81 Correct 15 ms 68436 KB n=2000
82 Correct 15 ms 68444 KB n=2000
83 Correct 15 ms 68700 KB n=2000
84 Correct 14 ms 68600 KB n=2000
85 Correct 14 ms 68444 KB n=2000
86 Correct 15 ms 68432 KB n=2000
87 Correct 15 ms 68432 KB n=2000
88 Correct 14 ms 66640 KB n=2000
89 Correct 14 ms 66640 KB n=2000
90 Correct 14 ms 68732 KB n=2000
91 Correct 14 ms 68432 KB n=2000
92 Correct 577 ms 133316 KB n=200000
93 Correct 602 ms 137032 KB n=200000
94 Correct 597 ms 140064 KB n=200000
95 Correct 563 ms 133832 KB n=200000
96 Correct 549 ms 134080 KB n=200000
97 Correct 694 ms 136240 KB n=200000
98 Correct 576 ms 134072 KB n=200000
99 Correct 711 ms 132764 KB n=200000
100 Correct 558 ms 133308 KB n=200000
101 Correct 715 ms 140928 KB n=200000
102 Correct 278 ms 134472 KB n=200000
103 Correct 276 ms 134472 KB n=200000
104 Correct 265 ms 134472 KB n=200000
105 Correct 275 ms 134008 KB n=200000
106 Correct 312 ms 134224 KB n=200000
107 Correct 280 ms 134216 KB n=200000
108 Correct 600 ms 132956 KB n=200000
109 Correct 662 ms 133192 KB n=200000
110 Correct 573 ms 133172 KB n=200000
111 Correct 518 ms 133816 KB n=200000
112 Correct 749 ms 140152 KB n=200000
113 Correct 717 ms 136152 KB n=200000
114 Correct 560 ms 134044 KB n=200000
115 Correct 791 ms 134216 KB n=200000
116 Correct 457 ms 133764 KB n=200000
117 Correct 617 ms 140360 KB n=200000
118 Correct 755 ms 135156 KB n=200000
119 Correct 529 ms 131420 KB n=200000
120 Correct 655 ms 138552 KB n=200000
121 Correct 723 ms 138364 KB n=200000
122 Correct 661 ms 141048 KB n=200000
123 Correct 343 ms 133768 KB n=200000
124 Correct 130 ms 83088 KB n=25264