Submission #1265520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265520		rayan_bd	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4093 ms	35792 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 10;
const int mxB = 26;
vector<int> adj[mxN];
int dp[mxN][mxB], depth[mxN], a[mxN], st[mxN], en[mxN], timer = -1;
void dfs(int u = 1, int par = 0){
    st[u] = ++timer;
    depth[u] = depth[par] + 1;
    dp[u][0] = par;
    for(int i = 1; i < mxB; ++i) dp[u][i] = dp[dp[u][i - 1]][i - 1];
    for(auto it : adj[u]){
        if(it ^ par){
            dfs(it, u);
        }
    }
    en[u] = ++timer;
}
bool in_subtree(int u, int v){
    return st[v] >= st[u] && en[v] <= en[u];
}
int kth(int u, int k){
    for(int i = 0; i < mxB; ++i){
        if(k & (1 << i)) u = dp[u][i];
    }
    return u;
}
int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    u = kth(u, depth[u] - depth[v]);
    if(u == v) return u;
    for(int i = mxB - 1; i >= 0; --i){
        if(dp[u][i] ^ dp[v][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[u][0];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q, u, v, l, r, idx, t;
    cin >> n >> m >> q;
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n - 1; ++i){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 0; i < m; ++i) cin >> a[i];
    dfs();
    for(int i = 0; i < q; ++i){
        cin >> t;
        if(t == 1){
            cin >> idx >> v;
            a[--idx] = v;
        }else{
            cin >> l >> r >> v;
            int ansl = -1, ansr = -1;
            for(int i = l - 1; i <= r - 1; ++i){
                if(a[i] == v) ansl = i + 1, ansr = i + 1;
                else if(i < (r - 1) && lca(a[i], a[i + 1]) == v) ansl = i + 1, ansr = i + 2;
            }
            cout << ansl << " " << ansr << "\n";
        }
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44