oj.uz

Submission #171666

# Submission time Handle Problem Language Result Execution time Memory
171666 2019-12-29T20:05:57 Z Lightning Birthday gift (IZhO18_treearray) C++14
56 / 100
 4000 ms 34156 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2e5 + 5;
const int LG = 18;

int n, m, q, a[N];
vector <int> g[N];
int up[N][20], tin[N], tout[N], timer;

void dfs(int v, int pr) {
	tin[v] = ++timer;
	up[v][0] = pr;
	for(int i = 1; i <= LG; ++i) {
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for(int to : g[v]) {
		if(to != pr) {
			dfs(to, v);
		}
	}
	tout[v] = ++timer;
}

bool is_ancestor(int a, int b) {
	return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

int lca(int a, int b) {
	if(is_ancestor(a, b)) return a;
	if(is_ancestor(b, a)) return b;
	for(int i = LG; i >= 0; --i) {
		if(!is_ancestor(up[a][i], b))
			a = up[a][i];
	}
	return up[a][0];
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i < n; ++i) {
		int p, q;
		cin >> p >> q;
		g[p].pb(q);
		g[q].pb(p);
	}
	dfs(1, 1);
	for(int i = 1; i <= m; ++i) {
		cin >> a[i];
	}
	for(int it = 1; it <= q; ++it) {
		int type;
		cin >> type;
		if(type == 1) {
			int pos, v;
			cin >> pos >> v;
			a[pos] = v;
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			pii ans = {-1, -1};	 
			for(int i = l; i <= r; ++i) {
				int res = a[i];
				int cur = i;
				while(i <= r && is_ancestor(v, a[i])) {
					res = lca(res, a[i]);
					++i;
				}
				if(res == v) {
					ans = {cur, i - 1};
				}
			}	
			cout << ans.F <<' '<< ans.S <<'\n';
		} 
	}
	return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5 
2 1 3 1
*/

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB n=5
2 Correct 6 ms 4988 KB n=100
3 Correct 6 ms 5112 KB n=100
4 Correct 6 ms 5112 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 4984 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5112 KB n=100
9 Correct 6 ms 4984 KB n=100
10 Correct 6 ms 4984 KB n=100
11 Correct 6 ms 4984 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 4984 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 6 ms 5112 KB n=100
17 Correct 6 ms 4988 KB n=100
18 Correct 6 ms 5112 KB n=100
19 Correct 6 ms 5092 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 7 ms 5112 KB n=100
22 Correct 6 ms 4984 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 4984 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 6 ms 5112 KB n=100
28 Correct 6 ms 5112 KB n=500
29 Correct 7 ms 5112 KB n=500
30 Correct 8 ms 5112 KB n=500
31 Correct 7 ms 5112 KB n=500
32 Correct 7 ms 5112 KB n=500
33 Correct 7 ms 5112 KB n=500
34 Correct 7 ms 5112 KB n=500
35 Correct 7 ms 5112 KB n=500
36 Correct 8 ms 5112 KB n=500
37 Correct 7 ms 5112 KB n=500
38 Correct 8 ms 5112 KB n=500
39 Correct 7 ms 5116 KB n=500
40 Correct 7 ms 5112 KB n=500
41 Correct 7 ms 5112 KB n=500
42 Correct 8 ms 5112 KB n=500
43 Correct 7 ms 5112 KB n=500
44 Correct 8 ms 5244 KB n=500
45 Correct 6 ms 5112 KB n=500
46 Correct 7 ms 5112 KB n=500
47 Correct 7 ms 5112 KB n=500
48 Correct 6 ms 5112 KB n=500
49 Correct 7 ms 5160 KB n=500
50 Correct 7 ms 5112 KB n=500
51 Correct 7 ms 5112 KB n=500
52 Correct 7 ms 5112 KB n=500
53 Correct 7 ms 5112 KB n=500
54 Correct 7 ms 5112 KB n=500
55 Correct 7 ms 5112 KB n=278
56 Correct 7 ms 5112 KB n=500
57 Correct 7 ms 5112 KB n=500
58 Correct 7 ms 5112 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB n=5
2 Correct 6 ms 4988 KB n=100
3 Correct 6 ms 5112 KB n=100
4 Correct 6 ms 5112 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 4984 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5112 KB n=100
9 Correct 6 ms 4984 KB n=100
10 Correct 6 ms 4984 KB n=100
11 Correct 6 ms 4984 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 4984 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 6 ms 5112 KB n=100
17 Correct 6 ms 4988 KB n=100
18 Correct 6 ms 5112 KB n=100
19 Correct 6 ms 5092 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 7 ms 5112 KB n=100
22 Correct 6 ms 4984 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 4984 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 6 ms 5112 KB n=100
28 Correct 6 ms 5112 KB n=500
29 Correct 7 ms 5112 KB n=500
30 Correct 8 ms 5112 KB n=500
31 Correct 7 ms 5112 KB n=500
32 Correct 7 ms 5112 KB n=500
33 Correct 7 ms 5112 KB n=500
34 Correct 7 ms 5112 KB n=500
35 Correct 7 ms 5112 KB n=500
36 Correct 8 ms 5112 KB n=500
37 Correct 7 ms 5112 KB n=500
38 Correct 8 ms 5112 KB n=500
39 Correct 7 ms 5116 KB n=500
40 Correct 7 ms 5112 KB n=500
41 Correct 7 ms 5112 KB n=500
42 Correct 8 ms 5112 KB n=500
43 Correct 7 ms 5112 KB n=500
44 Correct 8 ms 5244 KB n=500
45 Correct 6 ms 5112 KB n=500
46 Correct 7 ms 5112 KB n=500
47 Correct 7 ms 5112 KB n=500
48 Correct 6 ms 5112 KB n=500
49 Correct 7 ms 5160 KB n=500
50 Correct 7 ms 5112 KB n=500
51 Correct 7 ms 5112 KB n=500
52 Correct 7 ms 5112 KB n=500
53 Correct 7 ms 5112 KB n=500
54 Correct 7 ms 5112 KB n=500
55 Correct 7 ms 5112 KB n=278
56 Correct 7 ms 5112 KB n=500
57 Correct 7 ms 5112 KB n=500
58 Correct 7 ms 5112 KB n=500
59 Correct 11 ms 5368 KB n=2000
60 Correct 14 ms 5496 KB n=2000
61 Correct 21 ms 5368 KB n=2000
62 Correct 26 ms 5368 KB n=2000
63 Correct 11 ms 5368 KB n=2000
64 Correct 25 ms 5496 KB n=2000
65 Correct 11 ms 5368 KB n=2000
66 Correct 22 ms 5500 KB n=2000
67 Correct 17 ms 5368 KB n=2000
68 Correct 22 ms 5368 KB n=2000
69 Correct 23 ms 5468 KB n=2000
70 Correct 23 ms 5500 KB n=2000
71 Correct 23 ms 5368 KB n=2000
72 Correct 12 ms 5368 KB n=2000
73 Correct 12 ms 5368 KB n=2000
74 Correct 10 ms 5368 KB n=1844
75 Correct 12 ms 5368 KB n=2000
76 Correct 30 ms 5496 KB n=2000
77 Correct 28 ms 5368 KB n=2000
78 Correct 29 ms 5368 KB n=2000
79 Correct 11 ms 5368 KB n=2000
80 Correct 16 ms 5496 KB n=2000
81 Correct 22 ms 5368 KB n=2000
82 Correct 11 ms 5368 KB n=2000
83 Correct 17 ms 5368 KB n=2000
84 Correct 12 ms 5368 KB n=2000
85 Correct 17 ms 5368 KB n=2000
86 Correct 17 ms 5368 KB n=2000
87 Correct 13 ms 5352 KB n=2000
88 Correct 17 ms 5496 KB n=2000
89 Correct 17 ms 5496 KB n=2000
90 Correct 16 ms 5496 KB n=2000
91 Correct 25 ms 5368 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB n=5
2 Correct 6 ms 4988 KB n=100
3 Correct 6 ms 5112 KB n=100
4 Correct 6 ms 5112 KB n=100
5 Correct 6 ms 5112 KB n=100
6 Correct 6 ms 4984 KB n=100
7 Correct 6 ms 5112 KB n=100
8 Correct 6 ms 5112 KB n=100
9 Correct 6 ms 4984 KB n=100
10 Correct 6 ms 4984 KB n=100
11 Correct 6 ms 4984 KB n=100
12 Correct 6 ms 5112 KB n=100
13 Correct 6 ms 5112 KB n=100
14 Correct 6 ms 4984 KB n=100
15 Correct 6 ms 5112 KB n=100
16 Correct 6 ms 5112 KB n=100
17 Correct 6 ms 4988 KB n=100
18 Correct 6 ms 5112 KB n=100
19 Correct 6 ms 5092 KB n=100
20 Correct 6 ms 5112 KB n=100
21 Correct 7 ms 5112 KB n=100
22 Correct 6 ms 4984 KB n=100
23 Correct 6 ms 5112 KB n=100
24 Correct 6 ms 4984 KB n=100
25 Correct 6 ms 5112 KB n=100
26 Correct 6 ms 4984 KB n=12
27 Correct 6 ms 5112 KB n=100
28 Correct 6 ms 5112 KB n=500
29 Correct 7 ms 5112 KB n=500
30 Correct 8 ms 5112 KB n=500
31 Correct 7 ms 5112 KB n=500
32 Correct 7 ms 5112 KB n=500
33 Correct 7 ms 5112 KB n=500
34 Correct 7 ms 5112 KB n=500
35 Correct 7 ms 5112 KB n=500
36 Correct 8 ms 5112 KB n=500
37 Correct 7 ms 5112 KB n=500
38 Correct 8 ms 5112 KB n=500
39 Correct 7 ms 5116 KB n=500
40 Correct 7 ms 5112 KB n=500
41 Correct 7 ms 5112 KB n=500
42 Correct 8 ms 5112 KB n=500
43 Correct 7 ms 5112 KB n=500
44 Correct 8 ms 5244 KB n=500
45 Correct 6 ms 5112 KB n=500
46 Correct 7 ms 5112 KB n=500
47 Correct 7 ms 5112 KB n=500
48 Correct 6 ms 5112 KB n=500
49 Correct 7 ms 5160 KB n=500
50 Correct 7 ms 5112 KB n=500
51 Correct 7 ms 5112 KB n=500
52 Correct 7 ms 5112 KB n=500
53 Correct 7 ms 5112 KB n=500
54 Correct 7 ms 5112 KB n=500
55 Correct 7 ms 5112 KB n=278
56 Correct 7 ms 5112 KB n=500
57 Correct 7 ms 5112 KB n=500
58 Correct 7 ms 5112 KB n=500
59 Correct 11 ms 5368 KB n=2000
60 Correct 14 ms 5496 KB n=2000
61 Correct 21 ms 5368 KB n=2000
62 Correct 26 ms 5368 KB n=2000
63 Correct 11 ms 5368 KB n=2000
64 Correct 25 ms 5496 KB n=2000
65 Correct 11 ms 5368 KB n=2000
66 Correct 22 ms 5500 KB n=2000
67 Correct 17 ms 5368 KB n=2000
68 Correct 22 ms 5368 KB n=2000
69 Correct 23 ms 5468 KB n=2000
70 Correct 23 ms 5500 KB n=2000
71 Correct 23 ms 5368 KB n=2000
72 Correct 12 ms 5368 KB n=2000
73 Correct 12 ms 5368 KB n=2000
74 Correct 10 ms 5368 KB n=1844
75 Correct 12 ms 5368 KB n=2000
76 Correct 30 ms 5496 KB n=2000
77 Correct 28 ms 5368 KB n=2000
78 Correct 29 ms 5368 KB n=2000
79 Correct 11 ms 5368 KB n=2000
80 Correct 16 ms 5496 KB n=2000
81 Correct 22 ms 5368 KB n=2000
82 Correct 11 ms 5368 KB n=2000
83 Correct 17 ms 5368 KB n=2000
84 Correct 12 ms 5368 KB n=2000
85 Correct 17 ms 5368 KB n=2000
86 Correct 17 ms 5368 KB n=2000
87 Correct 13 ms 5352 KB n=2000
88 Correct 17 ms 5496 KB n=2000
89 Correct 17 ms 5496 KB n=2000
90 Correct 16 ms 5496 KB n=2000
91 Correct 25 ms 5368 KB n=2000
92 Execution timed out 4026 ms 34156 KB Time limit exceeded
93 Halted 0 ms 0 KB -