oj.uz

Submission #697836

# Submission time Handle Problem Language Result Execution time Memory
697836 2023-02-11T07:42:46 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
30 / 100
 4000 ms 5460 KB 
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

using namespace std;
const long long mod = (long long)1e9+7;
const int N = 200200;
int n, m, q, a[N], d[N], up[20][N];
vector<int> g[N];

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

int lca(int u, int v) {
	if(d[u] < d[v]) {
		int temp = u;
		u = v;
		v = temp;
	}
	for(int i = 18; i >= 0; i--){
		if(d[u] - (1<<i) >= d[v]) {
			u = up[i][u];
		}
	}
	if(u == v) return u;
	for(int i = 18; i >= 0; i--){
		if(up[i][u] != up[i][v]) {
			u = up[i][u];
			v = up[i][v];
		}
	}
	return up[0][v];
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));
    cin>>n>>m>>q;
    for (int i = 1; i<n; i++) {
        int x, y;
        cin>>x>>y;
        g[x].pb(y); g[y].pb(x);
    }
    for (int i = 1; i<=m; i++) {
        cin>>a[i];
    }
    dfs(1, 1);
    while (q--) {
        int t;
        cin>>t;
        if (t == 1) {
            int pos, v;
            cin>>pos>>v;
            a[pos] = v;
        } else {
            int l, r, v;
            cin>>l>>r>>v;
            int curr = 0;
            bool flag = false;
			for (int x = l; x <= r; x++) {
				for (int y = x; y <= r; y++) {
					if (y == x) curr = a[y];
					else curr = lca(curr, a[y]);
					if (curr == v) {
						cout<<x<<' '<<y<<'\n';
						flag = true;
						break;
					}
				// 	if (!isPar(v, curr)) break;
				}
				if (flag) break;
			}
			if (!flag)
			    cout<<"-1 -1\n";
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB n=5
2 Correct 4 ms 5076 KB n=100
3 Correct 4 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5032 KB n=100
6 Correct 16 ms 5152 KB n=100
7 Correct 16 ms 5152 KB n=100
8 Correct 5 ms 5076 KB n=100
9 Correct 4 ms 5076 KB n=100
10 Correct 11 ms 5204 KB n=100
11 Correct 9 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5036 KB n=100
14 Correct 3 ms 5076 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 6 ms 5076 KB n=100
18 Correct 6 ms 5060 KB n=100
19 Correct 3 ms 5076 KB n=100
20 Correct 5 ms 5076 KB n=100
21 Correct 5 ms 5028 KB n=100
22 Correct 4 ms 5204 KB n=100
23 Correct 7 ms 5136 KB n=100
24 Correct 7 ms 5076 KB n=100
25 Correct 4 ms 5032 KB n=100
26 Correct 3 ms 5032 KB n=12
27 Correct 9 ms 5076 KB n=100
28 Correct 5 ms 5192 KB n=500
29 Correct 280 ms 5212 KB n=500
30 Correct 185 ms 5204 KB n=500
31 Correct 224 ms 5204 KB n=500
32 Correct 10 ms 5148 KB n=500
33 Correct 170 ms 5204 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 238 ms 5208 KB n=500
36 Correct 1781 ms 5276 KB n=500
37 Correct 1795 ms 5204 KB n=500
38 Correct 1849 ms 5416 KB n=500
39 Correct 213 ms 5204 KB n=500
40 Correct 194 ms 5204 KB n=500
41 Correct 199 ms 5204 KB n=500
42 Correct 873 ms 5184 KB n=500
43 Correct 878 ms 5284 KB n=500
44 Correct 905 ms 5216 KB n=500
45 Correct 5 ms 5204 KB n=500
46 Correct 274 ms 5208 KB n=500
47 Correct 217 ms 5204 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 206 ms 5212 KB n=500
50 Correct 124 ms 5184 KB n=500
51 Correct 345 ms 5204 KB n=500
52 Correct 482 ms 5208 KB n=500
53 Correct 351 ms 5204 KB n=500
54 Correct 203 ms 5208 KB n=500
55 Correct 53 ms 5076 KB n=278
56 Correct 1688 ms 5208 KB n=500
57 Correct 1698 ms 5204 KB n=500
58 Correct 722 ms 5204 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB n=5
2 Correct 4 ms 5076 KB n=100
3 Correct 4 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5032 KB n=100
6 Correct 16 ms 5152 KB n=100
7 Correct 16 ms 5152 KB n=100
8 Correct 5 ms 5076 KB n=100
9 Correct 4 ms 5076 KB n=100
10 Correct 11 ms 5204 KB n=100
11 Correct 9 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5036 KB n=100
14 Correct 3 ms 5076 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 6 ms 5076 KB n=100
18 Correct 6 ms 5060 KB n=100
19 Correct 3 ms 5076 KB n=100
20 Correct 5 ms 5076 KB n=100
21 Correct 5 ms 5028 KB n=100
22 Correct 4 ms 5204 KB n=100
23 Correct 7 ms 5136 KB n=100
24 Correct 7 ms 5076 KB n=100
25 Correct 4 ms 5032 KB n=100
26 Correct 3 ms 5032 KB n=12
27 Correct 9 ms 5076 KB n=100
28 Correct 5 ms 5192 KB n=500
29 Correct 280 ms 5212 KB n=500
30 Correct 185 ms 5204 KB n=500
31 Correct 224 ms 5204 KB n=500
32 Correct 10 ms 5148 KB n=500
33 Correct 170 ms 5204 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 238 ms 5208 KB n=500
36 Correct 1781 ms 5276 KB n=500
37 Correct 1795 ms 5204 KB n=500
38 Correct 1849 ms 5416 KB n=500
39 Correct 213 ms 5204 KB n=500
40 Correct 194 ms 5204 KB n=500
41 Correct 199 ms 5204 KB n=500
42 Correct 873 ms 5184 KB n=500
43 Correct 878 ms 5284 KB n=500
44 Correct 905 ms 5216 KB n=500
45 Correct 5 ms 5204 KB n=500
46 Correct 274 ms 5208 KB n=500
47 Correct 217 ms 5204 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 206 ms 5212 KB n=500
50 Correct 124 ms 5184 KB n=500
51 Correct 345 ms 5204 KB n=500
52 Correct 482 ms 5208 KB n=500
53 Correct 351 ms 5204 KB n=500
54 Correct 203 ms 5208 KB n=500
55 Correct 53 ms 5076 KB n=278
56 Correct 1688 ms 5208 KB n=500
57 Correct 1698 ms 5204 KB n=500
58 Correct 722 ms 5204 KB n=500
59 Correct 118 ms 5408 KB n=2000
60 Execution timed out 4066 ms 5460 KB Time limit exceeded
61 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB n=5
2 Correct 4 ms 5076 KB n=100
3 Correct 4 ms 5032 KB n=100
4 Correct 3 ms 5076 KB n=100
5 Correct 3 ms 5032 KB n=100
6 Correct 16 ms 5152 KB n=100
7 Correct 16 ms 5152 KB n=100
8 Correct 5 ms 5076 KB n=100
9 Correct 4 ms 5076 KB n=100
10 Correct 11 ms 5204 KB n=100
11 Correct 9 ms 5076 KB n=100
12 Correct 3 ms 5076 KB n=100
13 Correct 3 ms 5036 KB n=100
14 Correct 3 ms 5076 KB n=100
15 Correct 3 ms 5076 KB n=100
16 Correct 3 ms 5076 KB n=100
17 Correct 6 ms 5076 KB n=100
18 Correct 6 ms 5060 KB n=100
19 Correct 3 ms 5076 KB n=100
20 Correct 5 ms 5076 KB n=100
21 Correct 5 ms 5028 KB n=100
22 Correct 4 ms 5204 KB n=100
23 Correct 7 ms 5136 KB n=100
24 Correct 7 ms 5076 KB n=100
25 Correct 4 ms 5032 KB n=100
26 Correct 3 ms 5032 KB n=12
27 Correct 9 ms 5076 KB n=100
28 Correct 5 ms 5192 KB n=500
29 Correct 280 ms 5212 KB n=500
30 Correct 185 ms 5204 KB n=500
31 Correct 224 ms 5204 KB n=500
32 Correct 10 ms 5148 KB n=500
33 Correct 170 ms 5204 KB n=500
34 Correct 3 ms 5204 KB n=500
35 Correct 238 ms 5208 KB n=500
36 Correct 1781 ms 5276 KB n=500
37 Correct 1795 ms 5204 KB n=500
38 Correct 1849 ms 5416 KB n=500
39 Correct 213 ms 5204 KB n=500
40 Correct 194 ms 5204 KB n=500
41 Correct 199 ms 5204 KB n=500
42 Correct 873 ms 5184 KB n=500
43 Correct 878 ms 5284 KB n=500
44 Correct 905 ms 5216 KB n=500
45 Correct 5 ms 5204 KB n=500
46 Correct 274 ms 5208 KB n=500
47 Correct 217 ms 5204 KB n=500
48 Correct 3 ms 5204 KB n=500
49 Correct 206 ms 5212 KB n=500
50 Correct 124 ms 5184 KB n=500
51 Correct 345 ms 5204 KB n=500
52 Correct 482 ms 5208 KB n=500
53 Correct 351 ms 5204 KB n=500
54 Correct 203 ms 5208 KB n=500
55 Correct 53 ms 5076 KB n=278
56 Correct 1688 ms 5208 KB n=500
57 Correct 1698 ms 5204 KB n=500
58 Correct 722 ms 5204 KB n=500
59 Correct 118 ms 5408 KB n=2000
60 Execution timed out 4066 ms 5460 KB Time limit exceeded
61 Halted 0 ms 0 KB -