oj.uz

Submission #525429

# Submission time Handle Problem Language Result Execution time Memory
525429 2022-02-11T15:34:52 Z s_samchenko Birthday gift (IZhO18_treearray) C++17
30 / 100
 4000 ms 1072 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 <= 19; ++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 = 19, 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 = 19; 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> (20));
	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 252 KB n=100
3 Correct 1 ms 316 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 312 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 312 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 2 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 2 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 312 KB n=100
23 Correct 8 ms 332 KB n=100
24 Correct 10 ms 332 KB n=100
25 Correct 8 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 336 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 252 KB n=100
3 Correct 1 ms 316 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 312 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 312 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 2 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 2 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 312 KB n=100
23 Correct 8 ms 332 KB n=100
24 Correct 10 ms 332 KB n=100
25 Correct 8 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 336 KB n=100
28 Correct 5 ms 460 KB n=500
29 Correct 28 ms 460 KB n=500
30 Correct 25 ms 464 KB n=500
31 Correct 31 ms 464 KB n=500
32 Correct 6 ms 460 KB n=500
33 Correct 31 ms 464 KB n=500
34 Correct 6 ms 464 KB n=500
35 Correct 30 ms 464 KB n=500
36 Correct 19 ms 448 KB n=500
37 Correct 19 ms 460 KB n=500
38 Correct 19 ms 448 KB n=500
39 Correct 6 ms 460 KB n=500
40 Correct 5 ms 460 KB n=500
41 Correct 6 ms 448 KB n=500
42 Correct 11 ms 456 KB n=500
43 Correct 12 ms 460 KB n=500
44 Correct 11 ms 464 KB n=500
45 Correct 5 ms 464 KB n=500
46 Correct 29 ms 460 KB n=500
47 Correct 24 ms 460 KB n=500
48 Correct 4 ms 460 KB n=500
49 Correct 17 ms 460 KB n=500
50 Correct 2 ms 460 KB n=500
51 Correct 18 ms 460 KB n=500
52 Correct 20 ms 468 KB n=500
53 Correct 16 ms 468 KB n=500
54 Correct 1310 ms 452 KB n=500
55 Correct 10 ms 396 KB n=278
56 Correct 2569 ms 460 KB n=500
57 Correct 2672 ms 460 KB n=500
58 Correct 9 ms 460 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 252 KB n=100
3 Correct 1 ms 316 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 312 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 312 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 2 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 2 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 312 KB n=100
23 Correct 8 ms 332 KB n=100
24 Correct 10 ms 332 KB n=100
25 Correct 8 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 336 KB n=100
28 Correct 5 ms 460 KB n=500
29 Correct 28 ms 460 KB n=500
30 Correct 25 ms 464 KB n=500
31 Correct 31 ms 464 KB n=500
32 Correct 6 ms 460 KB n=500
33 Correct 31 ms 464 KB n=500
34 Correct 6 ms 464 KB n=500
35 Correct 30 ms 464 KB n=500
36 Correct 19 ms 448 KB n=500
37 Correct 19 ms 460 KB n=500
38 Correct 19 ms 448 KB n=500
39 Correct 6 ms 460 KB n=500
40 Correct 5 ms 460 KB n=500
41 Correct 6 ms 448 KB n=500
42 Correct 11 ms 456 KB n=500
43 Correct 12 ms 460 KB n=500
44 Correct 11 ms 464 KB n=500
45 Correct 5 ms 464 KB n=500
46 Correct 29 ms 460 KB n=500
47 Correct 24 ms 460 KB n=500
48 Correct 4 ms 460 KB n=500
49 Correct 17 ms 460 KB n=500
50 Correct 2 ms 460 KB n=500
51 Correct 18 ms 460 KB n=500
52 Correct 20 ms 468 KB n=500
53 Correct 16 ms 468 KB n=500
54 Correct 1310 ms 452 KB n=500
55 Correct 10 ms 396 KB n=278
56 Correct 2569 ms 460 KB n=500
57 Correct 2672 ms 460 KB n=500
58 Correct 9 ms 460 KB n=500
59 Correct 91 ms 904 KB n=2000
60 Correct 673 ms 968 KB n=2000
61 Correct 607 ms 1068 KB n=2000
62 Correct 747 ms 916 KB n=2000
63 Correct 82 ms 900 KB n=2000
64 Correct 711 ms 916 KB n=2000
65 Correct 78 ms 900 KB n=2000
66 Correct 747 ms 1072 KB n=2000
67 Correct 125 ms 896 KB n=2000
68 Correct 780 ms 940 KB n=2000
69 Correct 320 ms 904 KB n=2000
70 Correct 300 ms 844 KB n=2000
71 Correct 310 ms 900 KB n=2000
72 Correct 82 ms 972 KB n=2000
73 Correct 82 ms 844 KB n=2000
74 Correct 61 ms 848 KB n=1844
75 Correct 79 ms 904 KB n=2000
76 Correct 186 ms 900 KB n=2000
77 Correct 183 ms 972 KB n=2000
78 Correct 188 ms 888 KB n=2000
79 Correct 69 ms 896 KB n=2000
80 Correct 537 ms 956 KB n=2000
81 Correct 509 ms 844 KB n=2000
82 Correct 63 ms 844 KB n=2000
83 Correct 545 ms 964 KB n=2000
84 Correct 40 ms 916 KB n=2000
85 Correct 583 ms 920 KB n=2000
86 Correct 285 ms 912 KB n=2000
87 Correct 40 ms 844 KB n=2000
88 Execution timed out 4069 ms 972 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 252 KB n=100
3 Correct 1 ms 316 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 332 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 312 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 312 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 2 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 2 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 312 KB n=100
23 Correct 8 ms 332 KB n=100
24 Correct 10 ms 332 KB n=100
25 Correct 8 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 336 KB n=100
28 Correct 5 ms 460 KB n=500
29 Correct 28 ms 460 KB n=500
30 Correct 25 ms 464 KB n=500
31 Correct 31 ms 464 KB n=500
32 Correct 6 ms 460 KB n=500
33 Correct 31 ms 464 KB n=500
34 Correct 6 ms 464 KB n=500
35 Correct 30 ms 464 KB n=500
36 Correct 19 ms 448 KB n=500
37 Correct 19 ms 460 KB n=500
38 Correct 19 ms 448 KB n=500
39 Correct 6 ms 460 KB n=500
40 Correct 5 ms 460 KB n=500
41 Correct 6 ms 448 KB n=500
42 Correct 11 ms 456 KB n=500
43 Correct 12 ms 460 KB n=500
44 Correct 11 ms 464 KB n=500
45 Correct 5 ms 464 KB n=500
46 Correct 29 ms 460 KB n=500
47 Correct 24 ms 460 KB n=500
48 Correct 4 ms 460 KB n=500
49 Correct 17 ms 460 KB n=500
50 Correct 2 ms 460 KB n=500
51 Correct 18 ms 460 KB n=500
52 Correct 20 ms 468 KB n=500
53 Correct 16 ms 468 KB n=500
54 Correct 1310 ms 452 KB n=500
55 Correct 10 ms 396 KB n=278
56 Correct 2569 ms 460 KB n=500
57 Correct 2672 ms 460 KB n=500
58 Correct 9 ms 460 KB n=500
59 Correct 91 ms 904 KB n=2000
60 Correct 673 ms 968 KB n=2000
61 Correct 607 ms 1068 KB n=2000
62 Correct 747 ms 916 KB n=2000
63 Correct 82 ms 900 KB n=2000
64 Correct 711 ms 916 KB n=2000
65 Correct 78 ms 900 KB n=2000
66 Correct 747 ms 1072 KB n=2000
67 Correct 125 ms 896 KB n=2000
68 Correct 780 ms 940 KB n=2000
69 Correct 320 ms 904 KB n=2000
70 Correct 300 ms 844 KB n=2000
71 Correct 310 ms 900 KB n=2000
72 Correct 82 ms 972 KB n=2000
73 Correct 82 ms 844 KB n=2000
74 Correct 61 ms 848 KB n=1844
75 Correct 79 ms 904 KB n=2000
76 Correct 186 ms 900 KB n=2000
77 Correct 183 ms 972 KB n=2000
78 Correct 188 ms 888 KB n=2000
79 Correct 69 ms 896 KB n=2000
80 Correct 537 ms 956 KB n=2000
81 Correct 509 ms 844 KB n=2000
82 Correct 63 ms 844 KB n=2000
83 Correct 545 ms 964 KB n=2000
84 Correct 40 ms 916 KB n=2000
85 Correct 583 ms 920 KB n=2000
86 Correct 285 ms 912 KB n=2000
87 Correct 40 ms 844 KB n=2000
88 Execution timed out 4069 ms 972 KB Time limit exceeded
89 Halted 0 ms 0 KB -