oj.uz

Submission #642932

# Submission time Handle Problem Language Result Execution time Memory
642932 2022-09-20T20:45:56 Z luanaamorim Birthday gift (IZhO18_treearray) C++14
100 / 100
 1056 ms 85492 KB 
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#define dbug(x) cout << (#x) << " -> " << x << endl
#define ll long long
#define INF (1e9)
#define MAX (int) (2e5 + 5)
#define MOD 1000000007
#define par pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(x) (int) ((x).size())
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define lsb(x) (x & -x)
#define W(x) cout << #x << ": " << x << endl
#define Wii(x) cout << x.first << ' ' << x.second << endl
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MAXL 20

using namespace std;

int n, m, q, a, op, t, b, c, arr[MAX], resp[MAX], tin[MAX], tout[MAX], up[MAX][MAXL];
vector<int> grafo[MAX];
set<int> freq[MAX], alone[MAX];

void dfs(int u, int p)
{
	tin[u] = ++t;
	up[u][0] = p;
	for (int i = 1; i < MAXL; i++)
		up[u][i] = up[up[u][i-1]][i-1];
	for (int v : grafo[u])
		if (v != p) dfs(v, u);
	tout[u] = ++t;
}

int is_anc(int u, int v)
{
	return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

int LCA(int u, int v)
{
	if (is_anc(u, v)) return u;
	if (is_anc(v, u)) return v;
	for (int i = MAXL-1; i >= 0; i--)
		if (!is_anc(up[u][i], v)) u = up[u][i];
	
	return up[u][0];
}

int main()
{_
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++)
	{
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}

	dfs(1, 1);
	for (int i = 1; i <= m; i++)
	{
		cin >> arr[i];
		alone[arr[i]].insert(i);
		resp[i] = LCA(arr[i], arr[i-1]);
		if (i>1) freq[resp[i]].insert(i);
	}

	while (q--)
	{
		cin >> op >> a >> b;
		if (op&1) 
		{
			int idx = a;
			alone[arr[idx]].erase(idx);
			freq[resp[idx]].erase(idx);
			freq[resp[idx+1]].erase(idx+1);
			arr[idx] = b;
			arr[0] = arr[1];
			alone[arr[idx]].insert(idx);
			resp[idx] = LCA(arr[idx], arr[idx-1]);
			resp[idx+1] = LCA(arr[idx+1], arr[idx]);
			freq[resp[idx]].insert(idx);
			freq[resp[idx+1]].insert(idx+1);

		}
		else 
		{
			cin >> c;
			auto idx = alone[c].lower_bound(a);
			if (idx != alone[c].end() && *idx <= b) 
			{
				cout << (*idx) << ' ' << (*idx) << endl;
				continue;
			}

			idx = freq[c].upper_bound(a);
			if (idx == freq[c].end() || *idx > b) 
			{
				cout << -1 << ' ' << -1 << endl;
				continue;
			}

			cout << (*idx)-1 << ' ' << (*idx) << endl;
		}
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23720 KB n=5
2 Correct 14 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23760 KB n=100
6 Correct 12 ms 23808 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 13 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 13 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 13 ms 23764 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23808 KB n=100
20 Correct 12 ms 23828 KB n=100
21 Correct 14 ms 23764 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 15 ms 23764 KB n=100
25 Correct 15 ms 23756 KB n=100
26 Correct 13 ms 23832 KB n=12
27 Correct 15 ms 23812 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23720 KB n=5
2 Correct 14 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23760 KB n=100
6 Correct 12 ms 23808 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 13 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 13 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 13 ms 23764 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23808 KB n=100
20 Correct 12 ms 23828 KB n=100
21 Correct 14 ms 23764 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 15 ms 23764 KB n=100
25 Correct 15 ms 23756 KB n=100
26 Correct 13 ms 23832 KB n=12
27 Correct 15 ms 23812 KB n=100
28 Correct 13 ms 23892 KB n=500
29 Correct 13 ms 23892 KB n=500
30 Correct 13 ms 23868 KB n=500
31 Correct 15 ms 23892 KB n=500
32 Correct 14 ms 23952 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 15 ms 24068 KB n=500
35 Correct 13 ms 23892 KB n=500
36 Correct 13 ms 23892 KB n=500
37 Correct 13 ms 23924 KB n=500
38 Correct 14 ms 23892 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 13 ms 23956 KB n=500
41 Correct 13 ms 23948 KB n=500
42 Correct 14 ms 23944 KB n=500
43 Correct 15 ms 24040 KB n=500
44 Correct 16 ms 23948 KB n=500
45 Correct 13 ms 23892 KB n=500
46 Correct 14 ms 23952 KB n=500
47 Correct 13 ms 23892 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 13 ms 23948 KB n=500
50 Correct 13 ms 23892 KB n=500
51 Correct 13 ms 23940 KB n=500
52 Correct 16 ms 23892 KB n=500
53 Correct 14 ms 23956 KB n=500
54 Correct 13 ms 23900 KB n=500
55 Correct 13 ms 23816 KB n=278
56 Correct 13 ms 23892 KB n=500
57 Correct 13 ms 23948 KB n=500
58 Correct 14 ms 23952 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23720 KB n=5
2 Correct 14 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23760 KB n=100
6 Correct 12 ms 23808 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 13 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 13 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 13 ms 23764 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23808 KB n=100
20 Correct 12 ms 23828 KB n=100
21 Correct 14 ms 23764 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 15 ms 23764 KB n=100
25 Correct 15 ms 23756 KB n=100
26 Correct 13 ms 23832 KB n=12
27 Correct 15 ms 23812 KB n=100
28 Correct 13 ms 23892 KB n=500
29 Correct 13 ms 23892 KB n=500
30 Correct 13 ms 23868 KB n=500
31 Correct 15 ms 23892 KB n=500
32 Correct 14 ms 23952 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 15 ms 24068 KB n=500
35 Correct 13 ms 23892 KB n=500
36 Correct 13 ms 23892 KB n=500
37 Correct 13 ms 23924 KB n=500
38 Correct 14 ms 23892 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 13 ms 23956 KB n=500
41 Correct 13 ms 23948 KB n=500
42 Correct 14 ms 23944 KB n=500
43 Correct 15 ms 24040 KB n=500
44 Correct 16 ms 23948 KB n=500
45 Correct 13 ms 23892 KB n=500
46 Correct 14 ms 23952 KB n=500
47 Correct 13 ms 23892 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 13 ms 23948 KB n=500
50 Correct 13 ms 23892 KB n=500
51 Correct 13 ms 23940 KB n=500
52 Correct 16 ms 23892 KB n=500
53 Correct 14 ms 23956 KB n=500
54 Correct 13 ms 23900 KB n=500
55 Correct 13 ms 23816 KB n=278
56 Correct 13 ms 23892 KB n=500
57 Correct 13 ms 23948 KB n=500
58 Correct 14 ms 23952 KB n=500
59 Correct 17 ms 24336 KB n=2000
60 Correct 20 ms 24404 KB n=2000
61 Correct 16 ms 24288 KB n=2000
62 Correct 17 ms 24336 KB n=2000
63 Correct 19 ms 24344 KB n=2000
64 Correct 17 ms 24404 KB n=2000
65 Correct 19 ms 24404 KB n=2000
66 Correct 16 ms 24276 KB n=2000
67 Correct 17 ms 24344 KB n=2000
68 Correct 16 ms 24276 KB n=2000
69 Correct 17 ms 24304 KB n=2000
70 Correct 18 ms 24260 KB n=2000
71 Correct 19 ms 24336 KB n=2000
72 Correct 19 ms 24276 KB n=2000
73 Correct 17 ms 24332 KB n=2000
74 Correct 19 ms 24308 KB n=1844
75 Correct 18 ms 24276 KB n=2000
76 Correct 17 ms 24276 KB n=2000
77 Correct 17 ms 24336 KB n=2000
78 Correct 16 ms 24268 KB n=2000
79 Correct 16 ms 24276 KB n=2000
80 Correct 21 ms 24388 KB n=2000
81 Correct 16 ms 24332 KB n=2000
82 Correct 17 ms 24276 KB n=2000
83 Correct 16 ms 24336 KB n=2000
84 Correct 16 ms 24276 KB n=2000
85 Correct 16 ms 24284 KB n=2000
86 Correct 17 ms 24280 KB n=2000
87 Correct 16 ms 24340 KB n=2000
88 Correct 16 ms 24400 KB n=2000
89 Correct 16 ms 24324 KB n=2000
90 Correct 16 ms 24348 KB n=2000
91 Correct 17 ms 24344 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23720 KB n=5
2 Correct 14 ms 23764 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23760 KB n=100
6 Correct 12 ms 23808 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 13 ms 23764 KB n=100
9 Correct 14 ms 23764 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 13 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 13 ms 23764 KB n=100
16 Correct 13 ms 23764 KB n=100
17 Correct 13 ms 23764 KB n=100
18 Correct 13 ms 23764 KB n=100
19 Correct 12 ms 23808 KB n=100
20 Correct 12 ms 23828 KB n=100
21 Correct 14 ms 23764 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 15 ms 23764 KB n=100
25 Correct 15 ms 23756 KB n=100
26 Correct 13 ms 23832 KB n=12
27 Correct 15 ms 23812 KB n=100
28 Correct 13 ms 23892 KB n=500
29 Correct 13 ms 23892 KB n=500
30 Correct 13 ms 23868 KB n=500
31 Correct 15 ms 23892 KB n=500
32 Correct 14 ms 23952 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 15 ms 24068 KB n=500
35 Correct 13 ms 23892 KB n=500
36 Correct 13 ms 23892 KB n=500
37 Correct 13 ms 23924 KB n=500
38 Correct 14 ms 23892 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 13 ms 23956 KB n=500
41 Correct 13 ms 23948 KB n=500
42 Correct 14 ms 23944 KB n=500
43 Correct 15 ms 24040 KB n=500
44 Correct 16 ms 23948 KB n=500
45 Correct 13 ms 23892 KB n=500
46 Correct 14 ms 23952 KB n=500
47 Correct 13 ms 23892 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 13 ms 23948 KB n=500
50 Correct 13 ms 23892 KB n=500
51 Correct 13 ms 23940 KB n=500
52 Correct 16 ms 23892 KB n=500
53 Correct 14 ms 23956 KB n=500
54 Correct 13 ms 23900 KB n=500
55 Correct 13 ms 23816 KB n=278
56 Correct 13 ms 23892 KB n=500
57 Correct 13 ms 23948 KB n=500
58 Correct 14 ms 23952 KB n=500
59 Correct 17 ms 24336 KB n=2000
60 Correct 20 ms 24404 KB n=2000
61 Correct 16 ms 24288 KB n=2000
62 Correct 17 ms 24336 KB n=2000
63 Correct 19 ms 24344 KB n=2000
64 Correct 17 ms 24404 KB n=2000
65 Correct 19 ms 24404 KB n=2000
66 Correct 16 ms 24276 KB n=2000
67 Correct 17 ms 24344 KB n=2000
68 Correct 16 ms 24276 KB n=2000
69 Correct 17 ms 24304 KB n=2000
70 Correct 18 ms 24260 KB n=2000
71 Correct 19 ms 24336 KB n=2000
72 Correct 19 ms 24276 KB n=2000
73 Correct 17 ms 24332 KB n=2000
74 Correct 19 ms 24308 KB n=1844
75 Correct 18 ms 24276 KB n=2000
76 Correct 17 ms 24276 KB n=2000
77 Correct 17 ms 24336 KB n=2000
78 Correct 16 ms 24268 KB n=2000
79 Correct 16 ms 24276 KB n=2000
80 Correct 21 ms 24388 KB n=2000
81 Correct 16 ms 24332 KB n=2000
82 Correct 17 ms 24276 KB n=2000
83 Correct 16 ms 24336 KB n=2000
84 Correct 16 ms 24276 KB n=2000
85 Correct 16 ms 24284 KB n=2000
86 Correct 17 ms 24280 KB n=2000
87 Correct 16 ms 24340 KB n=2000
88 Correct 16 ms 24400 KB n=2000
89 Correct 16 ms 24324 KB n=2000
90 Correct 16 ms 24348 KB n=2000
91 Correct 17 ms 24344 KB n=2000
92 Correct 863 ms 76032 KB n=200000
93 Correct 818 ms 80996 KB n=200000
94 Correct 675 ms 84300 KB n=200000
95 Correct 782 ms 75876 KB n=200000
96 Correct 733 ms 75848 KB n=200000
97 Correct 883 ms 80028 KB n=200000
98 Correct 787 ms 75856 KB n=200000
99 Correct 891 ms 76052 KB n=200000
100 Correct 792 ms 76088 KB n=200000
101 Correct 649 ms 85492 KB n=200000
102 Correct 666 ms 77124 KB n=200000
103 Correct 643 ms 77044 KB n=200000
104 Correct 672 ms 77100 KB n=200000
105 Correct 695 ms 77540 KB n=200000
106 Correct 696 ms 77656 KB n=200000
107 Correct 678 ms 77436 KB n=200000
108 Correct 830 ms 75916 KB n=200000
109 Correct 874 ms 75980 KB n=200000
110 Correct 816 ms 75960 KB n=200000
111 Correct 837 ms 75332 KB n=200000
112 Correct 684 ms 84544 KB n=200000
113 Correct 896 ms 80060 KB n=200000
114 Correct 878 ms 75424 KB n=200000
115 Correct 1056 ms 77992 KB n=200000
116 Correct 826 ms 76036 KB n=200000
117 Correct 625 ms 84868 KB n=200000
118 Correct 903 ms 78776 KB n=200000
119 Correct 729 ms 76080 KB n=200000
120 Correct 571 ms 84404 KB n=200000
121 Correct 570 ms 84564 KB n=200000
122 Correct 573 ms 84776 KB n=200000
123 Correct 694 ms 77300 KB n=200000
124 Correct 196 ms 39088 KB n=25264