oj.uz

Submission #651241

# Submission time Handle Problem Language Result Execution time Memory
651241 2022-10-18T03:21:32 Z Astrayt Birthday gift (IZhO18_treearray) C++17
0 / 100
 15 ms 24976 KB 
#include <bits/stdc++.h>
#define pb push_back
#define lc (p << 1)
#define rc ((p << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
array<int, 1 << 20> P, dep;
array<int, 1 << 20> S;
array<array<int, 20>, 1 << 20> A;
array<vector<int>, 1 << 20> T;
void DFS(int u, int pre, int d){
    dep[u] = d;
    for(int v : T[u]){
        if(v == pre) continue;
        A[v][0] = u;
        DFS(v, u, d + 1);
    }
}
void DABO(int n){
    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            A[i][j] = A[A[i][j - 1]][j - 1];
        }
    }
}
int LCA(int a, int b){
    if(!a || !b) return a ? a : b;
    if(dep[a] >= dep[b]) swap(a, b);
    for(int i = 19; i >= 0; i--){
        if(dep[A[b][i]] >= dep[a]) b = A[b][i];
    }
    if(a == b) return b;
    for(int i = 19; i >= 0; i--){
        if(A[a][i] != A[b][i]) a = A[a][i], b = A[b][i];
    }
    return A[a][0];
}
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, m, q, u, v, t, l, r, p, can;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        T[u].pb(v), T[v].pb(u);
    }
    DFS(1, 0, 0);
    DABO(n);
    for(int i = 1; i <= m; i++){
        cin >> P[i];
    }
    while(q--){
        cin >> t >> l >> r;
        int p;
        if(t == 1){
            P[l] = r;
        }else{
            can = 0;
            cin >> v;
            for(int i = l; i <= r; i++){
                p = P[i];
                if(can) break;
                for(int j = i; j <= r; j++){
                    p = LCA(p, P[j]);
                    if(p == v){
                        cout << i << " " << j << "\n";
                        can = 1;
                        break;
                    }
                    if(dep[p] <= dep[v]) break;
                }
            }
            if(!can) cout << "-1 -1\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
*/

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:40:33: warning: unused variable 'p' [-Wunused-variable]
   40 |     int n, m, q, u, v, t, l, r, p, can;
      |                                 ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB n=5
2 Correct 14 ms 24916 KB n=100
3 Correct 13 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 15 ms 24928 KB n=100
6 Correct 15 ms 24976 KB n=100
7 Correct 14 ms 24916 KB n=100
8 Correct 15 ms 24868 KB n=100
9 Correct 14 ms 24976 KB n=100
10 Correct 14 ms 24916 KB n=100
11 Correct 13 ms 24972 KB n=100
12 Correct 13 ms 24952 KB n=100
13 Correct 14 ms 24860 KB n=100
14 Correct 14 ms 24916 KB n=100
15 Incorrect 14 ms 24916 KB Jury has the answer but participant has not
16 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB n=5
2 Correct 14 ms 24916 KB n=100
3 Correct 13 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 15 ms 24928 KB n=100
6 Correct 15 ms 24976 KB n=100
7 Correct 14 ms 24916 KB n=100
8 Correct 15 ms 24868 KB n=100
9 Correct 14 ms 24976 KB n=100
10 Correct 14 ms 24916 KB n=100
11 Correct 13 ms 24972 KB n=100
12 Correct 13 ms 24952 KB n=100
13 Correct 14 ms 24860 KB n=100
14 Correct 14 ms 24916 KB n=100
15 Incorrect 14 ms 24916 KB Jury has the answer but participant has not
16 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB n=5
2 Correct 14 ms 24916 KB n=100
3 Correct 13 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 15 ms 24928 KB n=100
6 Correct 15 ms 24976 KB n=100
7 Correct 14 ms 24916 KB n=100
8 Correct 15 ms 24868 KB n=100
9 Correct 14 ms 24976 KB n=100
10 Correct 14 ms 24916 KB n=100
11 Correct 13 ms 24972 KB n=100
12 Correct 13 ms 24952 KB n=100
13 Correct 14 ms 24860 KB n=100
14 Correct 14 ms 24916 KB n=100
15 Incorrect 14 ms 24916 KB Jury has the answer but participant has not
16 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB n=5
2 Correct 14 ms 24916 KB n=100
3 Correct 13 ms 24916 KB n=100
4 Correct 14 ms 24916 KB n=100
5 Correct 15 ms 24928 KB n=100
6 Correct 15 ms 24976 KB n=100
7 Correct 14 ms 24916 KB n=100
8 Correct 15 ms 24868 KB n=100
9 Correct 14 ms 24976 KB n=100
10 Correct 14 ms 24916 KB n=100
11 Correct 13 ms 24972 KB n=100
12 Correct 13 ms 24952 KB n=100
13 Correct 14 ms 24860 KB n=100
14 Correct 14 ms 24916 KB n=100
15 Incorrect 14 ms 24916 KB Jury has the answer but participant has not
16 Halted 0 ms 0 KB -