Submission #651239

#	Time	Username	Problem	Language	Result	Execution time	Memory
651239		Astrayt	Birthday gift (IZhO18_treearray)	C++17	0 / 100	19 ms	25032 KiB

treearray

#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 (stderr)

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44