Submission #1100254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100254		vjudge1	Birthday gift (IZhO18_treearray)	C++17	0 / 100	2 ms	11260 KiB

treearray

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 200002;
const int lo = 18;
int n, m, q;
vector<int> t[maxn];
int parent[maxn][lo]; 
int depth[maxn]; 
int tin[maxn], tout[maxn], timer = 0; 
vector<int> a; 

void dfs(int v, int p) {
    tin[v] = timer++;
    parent[v][0] = p; 
    for (int i = 1; i < lo; ++i) {
        parent[v][i] = parent[parent[v][i - 1]][i - 1];
    }
    for (int u : t[v]) {
        if (u != p) {
            depth[u] = depth[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = timer++;
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int lca(int u, int v) {
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;
    for (int i = lo - 1; i >= 0; --i) {
        if (!anc(parent[u][i], v)) {
            u = parent[u][i];
        }
    }
    return parent[u][0];
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0);
    
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        t[u].pb(v);
        t[v].pb(u);
    }
    dfs(1, 1);
    
    a.resize(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }

    while (q--) {
        int type;
        cin >> type;
        
        if (type == 1) {
            int pos, v;
            cin >> pos >> v;
            a[pos] = v; 
        } 
        else if (type == 2) {
            int l, r, v;
            cin >> l >> r >>v;
            
            int currlca = a[l];
            bool found = false;
            for (int i = l; i <= r; ++i) {
                currlca = lca(currlca, a[i]);
                if (currlca == v) {
                    cout << l << " " << i << endl;
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                cout << -1 << " " << -1 << endl;
            }
        }
    }
    
    return 0;
}

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