oj.uz

Submission #844912

# Submission time Handle Problem Language Result Execution time Memory
844912 2023-09-06T08:46:55 Z Darren0724 Birthday gift (IZhO18_treearray) C++17
56 / 100
 4000 ms 35932 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) x.begin(), x.end()
const int N = 200005;
const int K = __lg(N) + 1;
int n, m, q;
vector<int> adj[N], deep(N);
int jump[K][N];
void dfs(int k, int pa) {
    jump[0][k] = pa;
    for (int i = 1; i < K; i++) {
        jump[i][k] = jump[i - 1][jump[i - 1][k]];
    }
    for (int j : adj[k]) {
        if (j == pa) {
            continue;
        }
        deep[j] = deep[k] + 1;
        dfs(j, k);
    }
}
int lca(int a, int b) {
    if (deep[a] < deep[b]) {
        swap(a, b);
    }
    int p = deep[a] - deep[b];
    for (int i = 0; i < K; i++) {
        if ((1 << i) & p) {
            a = jump[i][a];
        }
    }
    if (a == b) {
        return a;
    }
    for (int i = K - 1; i >= 0; i--) {
        if (jump[i][a] != jump[i][b]) {
            a = jump[i][a];
            b = jump[i][b];
        }
    }
    return jump[0][a];
}
int up(int a, int b) {
    return lca(a, b) == b;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 1);
    vector<int> v(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < q; i++){
        int id; cin >> id;
        if (id == 1) {
            int a,b;cin>>a>>b;
            v[a]=b;
        } 
        else {
            int a,b,c;cin>>a>>b>>c;
            int y=-1;
            int p=0;
            int ans1=-1,ans2=-1;
            for(int j=a;j<=b;j++){
                if(!up(v[j],c)){
                    y=-1;
                }
                else{
                    if(y==-1){
                        p=j;
                        y=v[j];
                    }
                    else{
                        y=lca(y,v[j]);
                    }
                }
                if(y==c){
                    ans1=p,ans2=j;
                    break;
                }
            }
            cout<<ans1<<' '<<ans2<<endl;
        } 
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB n=5
2 Correct 4 ms 19800 KB n=100
3 Correct 3 ms 19800 KB n=100
4 Correct 3 ms 19800 KB n=100
5 Correct 3 ms 19804 KB n=100
6 Correct 3 ms 19800 KB n=100
7 Correct 3 ms 19800 KB n=100
8 Correct 3 ms 19800 KB n=100
9 Correct 3 ms 19804 KB n=100
10 Correct 4 ms 19844 KB n=100
11 Correct 3 ms 19800 KB n=100
12 Correct 3 ms 19800 KB n=100
13 Correct 3 ms 19804 KB n=100
14 Correct 3 ms 19800 KB n=100
15 Correct 3 ms 19804 KB n=100
16 Correct 3 ms 19800 KB n=100
17 Correct 3 ms 19800 KB n=100
18 Correct 3 ms 19800 KB n=100
19 Correct 3 ms 20056 KB n=100
20 Correct 3 ms 19800 KB n=100
21 Correct 4 ms 19800 KB n=100
22 Correct 3 ms 19804 KB n=100
23 Correct 3 ms 19800 KB n=100
24 Correct 4 ms 19800 KB n=100
25 Correct 3 ms 19804 KB n=100
26 Correct 3 ms 19804 KB n=12
27 Correct 4 ms 19800 KB n=100
28 Correct 4 ms 19800 KB n=500
29 Correct 6 ms 19800 KB n=500
30 Correct 5 ms 19800 KB n=500
31 Correct 5 ms 19800 KB n=500
32 Correct 4 ms 19800 KB n=500
33 Correct 5 ms 20056 KB n=500
34 Correct 4 ms 19800 KB n=500
35 Correct 5 ms 19800 KB n=500
36 Correct 8 ms 19800 KB n=500
37 Correct 8 ms 19800 KB n=500
38 Correct 9 ms 19800 KB n=500
39 Correct 6 ms 19800 KB n=500
40 Correct 6 ms 19800 KB n=500
41 Correct 6 ms 19800 KB n=500
42 Correct 6 ms 19800 KB n=500
43 Correct 6 ms 19800 KB n=500
44 Correct 6 ms 19804 KB n=500
45 Correct 3 ms 19800 KB n=500
46 Correct 6 ms 19800 KB n=500
47 Correct 5 ms 19800 KB n=500
48 Correct 4 ms 19800 KB n=500
49 Correct 5 ms 19800 KB n=500
50 Correct 5 ms 20056 KB n=500
51 Correct 6 ms 19800 KB n=500
52 Correct 7 ms 19800 KB n=500
53 Correct 6 ms 19800 KB n=500
54 Correct 7 ms 19800 KB n=500
55 Correct 4 ms 19800 KB n=278
56 Correct 12 ms 19804 KB n=500
57 Correct 12 ms 19800 KB n=500
58 Correct 8 ms 19800 KB n=500
59 Correct 5 ms 19800 KB n=2000
60 Correct 36 ms 20056 KB n=2000
61 Correct 33 ms 20056 KB n=2000
62 Correct 24 ms 19800 KB n=2000
63 Correct 5 ms 19800 KB n=2000
64 Correct 31 ms 19800 KB n=2000
65 Correct 6 ms 19800 KB n=2000
66 Correct 38 ms 20060 KB n=2000
67 Correct 6 ms 19800 KB n=2000
68 Correct 37 ms 20056 KB n=2000
69 Correct 76 ms 19992 KB n=2000
70 Correct 77 ms 19800 KB n=2000
71 Correct 74 ms 19800 KB n=2000
72 Correct 41 ms 19800 KB n=2000
73 Correct 42 ms 19996 KB n=2000
74 Correct 5 ms 19800 KB n=1844
75 Correct 42 ms 19804 KB n=2000
76 Correct 46 ms 19804 KB n=2000
77 Correct 44 ms 19800 KB n=2000
78 Correct 46 ms 19800 KB n=2000
79 Correct 5 ms 19800 KB n=2000
80 Correct 35 ms 20056 KB n=2000
81 Correct 28 ms 19800 KB n=2000
82 Correct 6 ms 19800 KB n=2000
83 Correct 31 ms 20056 KB n=2000
84 Correct 24 ms 19800 KB n=2000
85 Correct 46 ms 19800 KB n=2000
86 Correct 47 ms 19800 KB n=2000
87 Correct 25 ms 19800 KB n=2000
88 Correct 230 ms 20056 KB n=2000
89 Correct 232 ms 20080 KB n=2000
90 Correct 118 ms 20072 KB n=2000
91 Correct 78 ms 19996 KB n=2000
92 Correct 411 ms 35516 KB n=200000
93 Execution timed out 4030 ms 35932 KB Time limit exceeded
94 Halted 0 ms 0 KB -