oj.uz

Submission #525431

# Submission time Handle Problem Language Result Execution time Memory
525431 2022-02-11T15:37:13 Z s_samchenko Birthday gift (IZhO18_treearray) C++17
30 / 100
 4000 ms 972 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //bad
#pragma GCC target("avx,avx2")
#define ll long long
#define ull unsigned ll
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e15;
constexpr ll mod = 1e9+7;
const int N = 3e5+100, B = 430;

vector < vector <int> > g, up;
vector <int> d;

void dfs(int v = 1, int pr = 1, int h = 0){
	d[v] = h;
	up[v][0] = pr;
	for (int j = 1; j <= 11; ++j) up[v][j] = up[up[v][j-1]][j-1];
	for (auto to : g[v]){
		if (to == pr) continue;
		dfs(to, v, h+1);
	}
}

int lca(int u, int v){
	if (d[v] < d[u]) swap(u, v);
	for (int j = 11, H = d[v] - d[u]; j >= 0 && H; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 11; j >= 0; --j){
		int v1 = up[v][j], u1 = up[u][j];
		if (u1 != v1) u = u1, v = v1;
	}
	return up[v][0];
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	g.resize(n+1);
	up.resize(n+1, vector <int> (12));
	d.resize(n+1);

	for (int i = 1; i < n; ++i){
		int a, b; cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs();
	vector <int> a(m+1);
	for (int i = 1; i <= m; ++i) cin >> a[i];
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int pos, v; cin >> pos >> v;
			a[pos] = v;
			continue;
		}
		int l, r, v; cin >> l >> r >> v;
		int x = -1, y = -1;
		for (int i = l; i <= r; ++i){
			if (lca(a[i], v) != v) continue;
			if (a[i] == v) x = i, y = i;
			int w = a[i];
			for (int j = i + 1; j <= r; ++j){
				if (lca(a[j], v) != v) break;
				w = lca(w, a[j]);
				if (w == v){
					x = i, y = j;
					break;
				}
			}
		}
		cout << x << " " << y << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 204 KB n=100
4 Correct 1 ms 204 KB n=100
5 Correct 1 ms 204 KB n=100
6 Correct 1 ms 204 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 204 KB n=100
9 Correct 1 ms 204 KB n=100
10 Correct 1 ms 204 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 204 KB n=100
13 Correct 1 ms 204 KB n=100
14 Correct 1 ms 204 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 268 KB n=100
18 Correct 1 ms 204 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 204 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 5 ms 332 KB n=100
24 Correct 6 ms 332 KB n=100
25 Correct 5 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 204 KB n=100
28 Correct 3 ms 332 KB n=500
29 Correct 20 ms 444 KB n=500
30 Correct 19 ms 332 KB n=500
31 Correct 23 ms 332 KB n=500
32 Correct 4 ms 332 KB n=500
33 Correct 21 ms 332 KB n=500
34 Correct 3 ms 332 KB n=500
35 Correct 23 ms 444 KB n=500
36 Correct 12 ms 332 KB n=500
37 Correct 15 ms 332 KB n=500
38 Correct 12 ms 332 KB n=500
39 Correct 4 ms 332 KB n=500
40 Correct 3 ms 332 KB n=500
41 Correct 4 ms 332 KB n=500
42 Correct 8 ms 332 KB n=500
43 Correct 8 ms 332 KB n=500
44 Correct 8 ms 332 KB n=500
45 Correct 4 ms 332 KB n=500
46 Correct 24 ms 332 KB n=500
47 Correct 18 ms 440 KB n=500
48 Correct 2 ms 332 KB n=500
49 Correct 15 ms 444 KB n=500
50 Correct 2 ms 332 KB n=500
51 Correct 12 ms 332 KB n=500
52 Correct 15 ms 444 KB n=500
53 Correct 12 ms 332 KB n=500
54 Correct 734 ms 432 KB n=500
55 Correct 7 ms 332 KB n=278
56 Correct 1529 ms 420 KB n=500
57 Correct 1564 ms 420 KB n=500
58 Correct 6 ms 416 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 204 KB n=100
4 Correct 1 ms 204 KB n=100
5 Correct 1 ms 204 KB n=100
6 Correct 1 ms 204 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 204 KB n=100
9 Correct 1 ms 204 KB n=100
10 Correct 1 ms 204 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 204 KB n=100
13 Correct 1 ms 204 KB n=100
14 Correct 1 ms 204 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 268 KB n=100
18 Correct 1 ms 204 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 204 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 5 ms 332 KB n=100
24 Correct 6 ms 332 KB n=100
25 Correct 5 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 204 KB n=100
28 Correct 3 ms 332 KB n=500
29 Correct 20 ms 444 KB n=500
30 Correct 19 ms 332 KB n=500
31 Correct 23 ms 332 KB n=500
32 Correct 4 ms 332 KB n=500
33 Correct 21 ms 332 KB n=500
34 Correct 3 ms 332 KB n=500
35 Correct 23 ms 444 KB n=500
36 Correct 12 ms 332 KB n=500
37 Correct 15 ms 332 KB n=500
38 Correct 12 ms 332 KB n=500
39 Correct 4 ms 332 KB n=500
40 Correct 3 ms 332 KB n=500
41 Correct 4 ms 332 KB n=500
42 Correct 8 ms 332 KB n=500
43 Correct 8 ms 332 KB n=500
44 Correct 8 ms 332 KB n=500
45 Correct 4 ms 332 KB n=500
46 Correct 24 ms 332 KB n=500
47 Correct 18 ms 440 KB n=500
48 Correct 2 ms 332 KB n=500
49 Correct 15 ms 444 KB n=500
50 Correct 2 ms 332 KB n=500
51 Correct 12 ms 332 KB n=500
52 Correct 15 ms 444 KB n=500
53 Correct 12 ms 332 KB n=500
54 Correct 734 ms 432 KB n=500
55 Correct 7 ms 332 KB n=278
56 Correct 1529 ms 420 KB n=500
57 Correct 1564 ms 420 KB n=500
58 Correct 6 ms 416 KB n=500
59 Correct 41 ms 740 KB n=2000
60 Correct 466 ms 820 KB n=2000
61 Correct 420 ms 840 KB n=2000
62 Correct 511 ms 752 KB n=2000
63 Correct 46 ms 716 KB n=2000
64 Correct 504 ms 972 KB n=2000
65 Correct 43 ms 732 KB n=2000
66 Correct 530 ms 796 KB n=2000
67 Correct 92 ms 720 KB n=2000
68 Correct 552 ms 892 KB n=2000
69 Correct 196 ms 728 KB n=2000
70 Correct 200 ms 720 KB n=2000
71 Correct 194 ms 716 KB n=2000
72 Correct 51 ms 736 KB n=2000
73 Correct 51 ms 716 KB n=2000
74 Correct 31 ms 588 KB n=1844
75 Correct 51 ms 740 KB n=2000
76 Correct 132 ms 740 KB n=2000
77 Correct 125 ms 836 KB n=2000
78 Correct 132 ms 716 KB n=2000
79 Correct 33 ms 740 KB n=2000
80 Correct 394 ms 836 KB n=2000
81 Correct 359 ms 716 KB n=2000
82 Correct 36 ms 736 KB n=2000
83 Correct 395 ms 784 KB n=2000
84 Correct 20 ms 716 KB n=2000
85 Correct 422 ms 876 KB n=2000
86 Correct 213 ms 756 KB n=2000
87 Correct 23 ms 716 KB n=2000
88 Execution timed out 4073 ms 716 KB Time limit exceeded
89 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 204 KB n=100
4 Correct 1 ms 204 KB n=100
5 Correct 1 ms 204 KB n=100
6 Correct 1 ms 204 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 204 KB n=100
9 Correct 1 ms 204 KB n=100
10 Correct 1 ms 204 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 204 KB n=100
13 Correct 1 ms 204 KB n=100
14 Correct 1 ms 204 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 268 KB n=100
18 Correct 1 ms 204 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 204 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 5 ms 332 KB n=100
24 Correct 6 ms 332 KB n=100
25 Correct 5 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 204 KB n=100
28 Correct 3 ms 332 KB n=500
29 Correct 20 ms 444 KB n=500
30 Correct 19 ms 332 KB n=500
31 Correct 23 ms 332 KB n=500
32 Correct 4 ms 332 KB n=500
33 Correct 21 ms 332 KB n=500
34 Correct 3 ms 332 KB n=500
35 Correct 23 ms 444 KB n=500
36 Correct 12 ms 332 KB n=500
37 Correct 15 ms 332 KB n=500
38 Correct 12 ms 332 KB n=500
39 Correct 4 ms 332 KB n=500
40 Correct 3 ms 332 KB n=500
41 Correct 4 ms 332 KB n=500
42 Correct 8 ms 332 KB n=500
43 Correct 8 ms 332 KB n=500
44 Correct 8 ms 332 KB n=500
45 Correct 4 ms 332 KB n=500
46 Correct 24 ms 332 KB n=500
47 Correct 18 ms 440 KB n=500
48 Correct 2 ms 332 KB n=500
49 Correct 15 ms 444 KB n=500
50 Correct 2 ms 332 KB n=500
51 Correct 12 ms 332 KB n=500
52 Correct 15 ms 444 KB n=500
53 Correct 12 ms 332 KB n=500
54 Correct 734 ms 432 KB n=500
55 Correct 7 ms 332 KB n=278
56 Correct 1529 ms 420 KB n=500
57 Correct 1564 ms 420 KB n=500
58 Correct 6 ms 416 KB n=500
59 Correct 41 ms 740 KB n=2000
60 Correct 466 ms 820 KB n=2000
61 Correct 420 ms 840 KB n=2000
62 Correct 511 ms 752 KB n=2000
63 Correct 46 ms 716 KB n=2000
64 Correct 504 ms 972 KB n=2000
65 Correct 43 ms 732 KB n=2000
66 Correct 530 ms 796 KB n=2000
67 Correct 92 ms 720 KB n=2000
68 Correct 552 ms 892 KB n=2000
69 Correct 196 ms 728 KB n=2000
70 Correct 200 ms 720 KB n=2000
71 Correct 194 ms 716 KB n=2000
72 Correct 51 ms 736 KB n=2000
73 Correct 51 ms 716 KB n=2000
74 Correct 31 ms 588 KB n=1844
75 Correct 51 ms 740 KB n=2000
76 Correct 132 ms 740 KB n=2000
77 Correct 125 ms 836 KB n=2000
78 Correct 132 ms 716 KB n=2000
79 Correct 33 ms 740 KB n=2000
80 Correct 394 ms 836 KB n=2000
81 Correct 359 ms 716 KB n=2000
82 Correct 36 ms 736 KB n=2000
83 Correct 395 ms 784 KB n=2000
84 Correct 20 ms 716 KB n=2000
85 Correct 422 ms 876 KB n=2000
86 Correct 213 ms 756 KB n=2000
87 Correct 23 ms 716 KB n=2000
88 Execution timed out 4073 ms 716 KB Time limit exceeded
89 Halted 0 ms 0 KB -