oj.uz

Submission #643761

# Submission time Handle Problem Language Result Execution time Memory
643761 2022-09-23T02:01:30 Z ymm Birthday gift (IZhO18_treearray) C++17
100 / 100
 3715 ms 95348 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 18;
const int S = 512;
int val[N], node[N];
vector<int> A[N];
vector<pii> ord;
int st[N];
pii rmq[lg+1][2*N];
int n, m, q;

__attribute__((optimize("O3,unroll-loops"),target("avx")))
int get_ind(int l, int r, int x, bool cnt)
{
	int *val = cnt? ::val: node;
	for (int i = l; i < r; i += S) {
		int j = min(i+S, r);
		int y = 0;
		Loop (k,i,j)
			y |= -(val[k] == x);
		if (y) {
			Loop (k,i,j)
				if (val[k] == x)
					return k;
		}
	}
	return -1;
}

void dfs(int v, int p, int h)
{
	st[v] = ord.size();
	ord.push_back({h, v});
	for (int u : A[v]) {
		if (u != p) {
			dfs(u, v, h+1);
			ord.push_back({h, v});
		}
	}
}

void rmq_init()
{
	int n = ord.size();
	Loop (i,0,n)
		rmq[0][i] = ord[i];
	Loop (i,0,lg)
		for (int j = 0; j + (2<<i) <= n; ++j)
			rmq[i+1][j] = min(rmq[i][j], rmq[i][j+(1<<i)]);
}
int get_anc(int v, int u)
{
	v = st[v]; u = st[u];
	if (v > u) swap(v, u);
	++u;
	int l = __lg(u - v);
	return min(rmq[l][v], rmq[l][u-(1<<l)]).second;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m >> q;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs(0, -1, 0);
	rmq_init();
	Loop (i,0,m) {
		cin >> node[i];
		--node[i];
	}
	Loop (i,0,m-1)
		val[i] = get_anc(node[i], node[i+1]);
	Loop (_,0,q) {
		//Loop (i,0,m-1) cout << val[i]+1 << ' '; cout << '\n';
		int t;
		cin >> t;
		if (t == 1) {
			int i, v;
			cin >> i >> v;
			--i; --v;
			node[i] = v;
			if (i > 0)
				val[i-1] = get_anc(node[i-1], node[i]);
			if (i < m-1)
				val[i] = get_anc(node[i], node[i+1]);
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			--l; --r; --v;
			int ans = get_ind(l, r, v, 1);
			if (ans < 0) {
				ans = get_ind(l, r+1, v, 0);
				if (ans < 0)
					cout << "-1 -1\n";
				else
					cout << ans+1 << ' ' << ans+1 << '\n';
			} else {
				cout << ans+1 << ' ' << ans+2 << '\n';
			}
		}
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB n=5
2 Correct 3 ms 5036 KB n=100
3 Correct 3 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5036 KB n=100
6 Correct 2 ms 5076 KB n=100
7 Correct 3 ms 5076 KB n=100
8 Correct 3 ms 5036 KB n=100
9 Correct 3 ms 5076 KB n=100
10 Correct 3 ms 5036 KB n=100
11 Correct 3 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5040 KB n=100
14 Correct 4 ms 5032 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 3 ms 5076 KB n=100
18 Correct 3 ms 5088 KB n=100
19 Correct 4 ms 5076 KB n=100
20 Correct 3 ms 5076 KB n=100
21 Correct 3 ms 5076 KB n=100
22 Correct 3 ms 5076 KB n=100
23 Correct 3 ms 5076 KB n=100
24 Correct 3 ms 5076 KB n=100
25 Correct 4 ms 5076 KB n=100
26 Correct 4 ms 5076 KB n=12
27 Correct 3 ms 5076 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB n=5
2 Correct 3 ms 5036 KB n=100
3 Correct 3 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5036 KB n=100
6 Correct 2 ms 5076 KB n=100
7 Correct 3 ms 5076 KB n=100
8 Correct 3 ms 5036 KB n=100
9 Correct 3 ms 5076 KB n=100
10 Correct 3 ms 5036 KB n=100
11 Correct 3 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5040 KB n=100
14 Correct 4 ms 5032 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 3 ms 5076 KB n=100
18 Correct 3 ms 5088 KB n=100
19 Correct 4 ms 5076 KB n=100
20 Correct 3 ms 5076 KB n=100
21 Correct 3 ms 5076 KB n=100
22 Correct 3 ms 5076 KB n=100
23 Correct 3 ms 5076 KB n=100
24 Correct 3 ms 5076 KB n=100
25 Correct 4 ms 5076 KB n=100
26 Correct 4 ms 5076 KB n=12
27 Correct 3 ms 5076 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 3 ms 5204 KB n=500
30 Correct 4 ms 5180 KB n=500
31 Correct 3 ms 5204 KB n=500
32 Correct 4 ms 5116 KB n=500
33 Correct 3 ms 5204 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 3 ms 5204 KB n=500
36 Correct 4 ms 5172 KB n=500
37 Correct 4 ms 5172 KB n=500
38 Correct 3 ms 5204 KB n=500
39 Correct 3 ms 5204 KB n=500
40 Correct 3 ms 5204 KB n=500
41 Correct 3 ms 5176 KB n=500
42 Correct 3 ms 5168 KB n=500
43 Correct 4 ms 5204 KB n=500
44 Correct 3 ms 5164 KB n=500
45 Correct 3 ms 5204 KB n=500
46 Correct 3 ms 5204 KB n=500
47 Correct 3 ms 5204 KB n=500
48 Correct 3 ms 5172 KB n=500
49 Correct 3 ms 5204 KB n=500
50 Correct 3 ms 5204 KB n=500
51 Correct 3 ms 5204 KB n=500
52 Correct 3 ms 5204 KB n=500
53 Correct 3 ms 5224 KB n=500
54 Correct 4 ms 5252 KB n=500
55 Correct 3 ms 5204 KB n=278
56 Correct 5 ms 5176 KB n=500
57 Correct 4 ms 5176 KB n=500
58 Correct 3 ms 5204 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB n=5
2 Correct 3 ms 5036 KB n=100
3 Correct 3 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5036 KB n=100
6 Correct 2 ms 5076 KB n=100
7 Correct 3 ms 5076 KB n=100
8 Correct 3 ms 5036 KB n=100
9 Correct 3 ms 5076 KB n=100
10 Correct 3 ms 5036 KB n=100
11 Correct 3 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5040 KB n=100
14 Correct 4 ms 5032 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 3 ms 5076 KB n=100
18 Correct 3 ms 5088 KB n=100
19 Correct 4 ms 5076 KB n=100
20 Correct 3 ms 5076 KB n=100
21 Correct 3 ms 5076 KB n=100
22 Correct 3 ms 5076 KB n=100
23 Correct 3 ms 5076 KB n=100
24 Correct 3 ms 5076 KB n=100
25 Correct 4 ms 5076 KB n=100
26 Correct 4 ms 5076 KB n=12
27 Correct 3 ms 5076 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 3 ms 5204 KB n=500
30 Correct 4 ms 5180 KB n=500
31 Correct 3 ms 5204 KB n=500
32 Correct 4 ms 5116 KB n=500
33 Correct 3 ms 5204 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 3 ms 5204 KB n=500
36 Correct 4 ms 5172 KB n=500
37 Correct 4 ms 5172 KB n=500
38 Correct 3 ms 5204 KB n=500
39 Correct 3 ms 5204 KB n=500
40 Correct 3 ms 5204 KB n=500
41 Correct 3 ms 5176 KB n=500
42 Correct 3 ms 5168 KB n=500
43 Correct 4 ms 5204 KB n=500
44 Correct 3 ms 5164 KB n=500
45 Correct 3 ms 5204 KB n=500
46 Correct 3 ms 5204 KB n=500
47 Correct 3 ms 5204 KB n=500
48 Correct 3 ms 5172 KB n=500
49 Correct 3 ms 5204 KB n=500
50 Correct 3 ms 5204 KB n=500
51 Correct 3 ms 5204 KB n=500
52 Correct 3 ms 5204 KB n=500
53 Correct 3 ms 5224 KB n=500
54 Correct 4 ms 5252 KB n=500
55 Correct 3 ms 5204 KB n=278
56 Correct 5 ms 5176 KB n=500
57 Correct 4 ms 5176 KB n=500
58 Correct 3 ms 5204 KB n=500
59 Correct 4 ms 5664 KB n=2000
60 Correct 5 ms 5816 KB n=2000
61 Correct 4 ms 5716 KB n=2000
62 Correct 4 ms 5648 KB n=2000
63 Correct 4 ms 5684 KB n=2000
64 Correct 5 ms 5692 KB n=2000
65 Correct 4 ms 5644 KB n=2000
66 Correct 5 ms 5716 KB n=2000
67 Correct 4 ms 5588 KB n=2000
68 Correct 4 ms 5716 KB n=2000
69 Correct 5 ms 5588 KB n=2000
70 Correct 6 ms 5652 KB n=2000
71 Correct 5 ms 5688 KB n=2000
72 Correct 5 ms 5688 KB n=2000
73 Correct 5 ms 5588 KB n=2000
74 Correct 4 ms 5632 KB n=1844
75 Correct 4 ms 5588 KB n=2000
76 Correct 4 ms 5684 KB n=2000
77 Correct 4 ms 5588 KB n=2000
78 Correct 4 ms 5588 KB n=2000
79 Correct 6 ms 5588 KB n=2000
80 Correct 5 ms 5716 KB n=2000
81 Correct 5 ms 5716 KB n=2000
82 Correct 5 ms 5588 KB n=2000
83 Correct 5 ms 5716 KB n=2000
84 Correct 5 ms 5636 KB n=2000
85 Correct 5 ms 5716 KB n=2000
86 Correct 5 ms 5716 KB n=2000
87 Correct 5 ms 5700 KB n=2000
88 Correct 4 ms 5844 KB n=2000
89 Correct 4 ms 5772 KB n=2000
90 Correct 5 ms 5844 KB n=2000
91 Correct 7 ms 5736 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB n=5
2 Correct 3 ms 5036 KB n=100
3 Correct 3 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5036 KB n=100
6 Correct 2 ms 5076 KB n=100
7 Correct 3 ms 5076 KB n=100
8 Correct 3 ms 5036 KB n=100
9 Correct 3 ms 5076 KB n=100
10 Correct 3 ms 5036 KB n=100
11 Correct 3 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5040 KB n=100
14 Correct 4 ms 5032 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 3 ms 5076 KB n=100
18 Correct 3 ms 5088 KB n=100
19 Correct 4 ms 5076 KB n=100
20 Correct 3 ms 5076 KB n=100
21 Correct 3 ms 5076 KB n=100
22 Correct 3 ms 5076 KB n=100
23 Correct 3 ms 5076 KB n=100
24 Correct 3 ms 5076 KB n=100
25 Correct 4 ms 5076 KB n=100
26 Correct 4 ms 5076 KB n=12
27 Correct 3 ms 5076 KB n=100
28 Correct 3 ms 5204 KB n=500
29 Correct 3 ms 5204 KB n=500
30 Correct 4 ms 5180 KB n=500
31 Correct 3 ms 5204 KB n=500
32 Correct 4 ms 5116 KB n=500
33 Correct 3 ms 5204 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 3 ms 5204 KB n=500
36 Correct 4 ms 5172 KB n=500
37 Correct 4 ms 5172 KB n=500
38 Correct 3 ms 5204 KB n=500
39 Correct 3 ms 5204 KB n=500
40 Correct 3 ms 5204 KB n=500
41 Correct 3 ms 5176 KB n=500
42 Correct 3 ms 5168 KB n=500
43 Correct 4 ms 5204 KB n=500
44 Correct 3 ms 5164 KB n=500
45 Correct 3 ms 5204 KB n=500
46 Correct 3 ms 5204 KB n=500
47 Correct 3 ms 5204 KB n=500
48 Correct 3 ms 5172 KB n=500
49 Correct 3 ms 5204 KB n=500
50 Correct 3 ms 5204 KB n=500
51 Correct 3 ms 5204 KB n=500
52 Correct 3 ms 5204 KB n=500
53 Correct 3 ms 5224 KB n=500
54 Correct 4 ms 5252 KB n=500
55 Correct 3 ms 5204 KB n=278
56 Correct 5 ms 5176 KB n=500
57 Correct 4 ms 5176 KB n=500
58 Correct 3 ms 5204 KB n=500
59 Correct 4 ms 5664 KB n=2000
60 Correct 5 ms 5816 KB n=2000
61 Correct 4 ms 5716 KB n=2000
62 Correct 4 ms 5648 KB n=2000
63 Correct 4 ms 5684 KB n=2000
64 Correct 5 ms 5692 KB n=2000
65 Correct 4 ms 5644 KB n=2000
66 Correct 5 ms 5716 KB n=2000
67 Correct 4 ms 5588 KB n=2000
68 Correct 4 ms 5716 KB n=2000
69 Correct 5 ms 5588 KB n=2000
70 Correct 6 ms 5652 KB n=2000
71 Correct 5 ms 5688 KB n=2000
72 Correct 5 ms 5688 KB n=2000
73 Correct 5 ms 5588 KB n=2000
74 Correct 4 ms 5632 KB n=1844
75 Correct 4 ms 5588 KB n=2000
76 Correct 4 ms 5684 KB n=2000
77 Correct 4 ms 5588 KB n=2000
78 Correct 4 ms 5588 KB n=2000
79 Correct 6 ms 5588 KB n=2000
80 Correct 5 ms 5716 KB n=2000
81 Correct 5 ms 5716 KB n=2000
82 Correct 5 ms 5588 KB n=2000
83 Correct 5 ms 5716 KB n=2000
84 Correct 5 ms 5636 KB n=2000
85 Correct 5 ms 5716 KB n=2000
86 Correct 5 ms 5716 KB n=2000
87 Correct 5 ms 5700 KB n=2000
88 Correct 4 ms 5844 KB n=2000
89 Correct 4 ms 5772 KB n=2000
90 Correct 5 ms 5844 KB n=2000
91 Correct 7 ms 5736 KB n=2000
92 Correct 233 ms 80264 KB n=200000
93 Correct 595 ms 87412 KB n=200000
94 Correct 652 ms 93048 KB n=200000
95 Correct 309 ms 80092 KB n=200000
96 Correct 227 ms 80088 KB n=200000
97 Correct 527 ms 85928 KB n=200000
98 Correct 210 ms 80096 KB n=200000
99 Correct 260 ms 79532 KB n=200000
100 Correct 225 ms 80124 KB n=200000
101 Correct 682 ms 95004 KB n=200000
102 Correct 1730 ms 81092 KB n=200000
103 Correct 1755 ms 81100 KB n=200000
104 Correct 1779 ms 81196 KB n=200000
105 Correct 342 ms 81036 KB n=200000
106 Correct 352 ms 80988 KB n=200000
107 Correct 408 ms 80992 KB n=200000
108 Correct 1010 ms 79980 KB n=200000
109 Correct 1120 ms 79812 KB n=200000
110 Correct 1051 ms 79888 KB n=200000
111 Correct 249 ms 80064 KB n=200000
112 Correct 630 ms 93832 KB n=200000
113 Correct 504 ms 86228 KB n=200000
114 Correct 219 ms 80076 KB n=200000
115 Correct 446 ms 82848 KB n=200000
116 Correct 1312 ms 80044 KB n=200000
117 Correct 1142 ms 94556 KB n=200000
118 Correct 1232 ms 84364 KB n=200000
119 Correct 1501 ms 80024 KB n=200000
120 Correct 3715 ms 94764 KB n=200000
121 Correct 3502 ms 94928 KB n=200000
122 Correct 1291 ms 95348 KB n=200000
123 Correct 1874 ms 81312 KB n=200000
124 Correct 77 ms 16904 KB n=25264