Submission #1242298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242298		Dedibeat	Birthday gift (IZhO18_treearray)	C++20	30 / 100	86 ms	584 KiB

treearray

#include <bits/stdc++.h>
 
using namespace std;

int n = 501, l;
vector<vector<int>> adj(n, vector<int>());

int timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

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

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    
    int m, q; cin >> n >> m >> q;
    for(int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        a -= 1, b -= 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> v(m);
    for(int &el : v) {
        cin >> el;
        el -= 1;
    }
    preprocess(0);
    for(int it = 0; it < q; it++) {
        int t, l, r; cin >> t >> l >> r;
        l -= 1, r -= 1;
        if(t == 1) v[l] = r;
        else {
            int u, x = -1, y = -1; cin >> u;
            u -= 1;
            for(int i = l; i <= r; i++) {
                int c = v[i];
                if(c == u) {
                    x = i + 1, y = i + 1;
                    break;
                }
                for(int j = i + 1; j <= r; j++) {
                    c = lca(c, v[j]);
                    if(c == u) {
                        x = i + 1, y = j + 1;
                        break;
                    }
                }
                if(x != -1) break;
            }
            cout << x << ' ' << y << '\n';
        }
    }
    return 0;
}

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