Submission #1162860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162860		SulA	Birthday gift (IZhO18_treearray)	C++20	56 / 100	16 ms	584 KiB

treearray

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount __builtin_popcountll
using namespace std;

vector<int> adj[2000];
int in[2000], out[2000], par[2000][11], t = 0;
int a[2000];

void dfs(int u = 0, int p = -1) {
    in[u] = t++;
    for (int v : adj[u]) if (v != p) {
        par[v][0] = u;
        for (int i = 1; i <= 10; i++)
            par[v][i] = par[par[v][i-1]][i-1];
        dfs(v, u);
    }
    out[u] = t++;
}

bool is_anc(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

int lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = 10; i >= 0; i--) if (!is_anc(par[v][i], u))
        v = par[v][i];
    return par[v][0];
}
int lca(vector<int> nodes) {
    if (nodes.empty()) return -1;
    int L = nodes[0];
    for (int x : nodes) L = lca(L, x);
    return L;
}

pair<int,int> solve(int l, int r, int u) {
    vector<int> subtree;
    int last = l;
    for (int i = l; i <= r; i++) {
        if (is_anc(u, a[i]))
            subtree.push_back(a[i]);
        else {
            if (lca(subtree) == u) return {last, i-1};
            subtree.clear();
            last = i+1;
        }
    }
    if (lca(subtree) == u) return {last, r};
    return {-2, -2};
}

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

    int n,m,q; cin>>n>>m>>q;
    for (int i = 0; i < n-1; i++) {
        int u,v; cin>>u>>v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
    }
    dfs();
    for (int i = 0; i < m; cin>>a[i], a[i++]--);
    while (q--) {
        cin>>t;
        if (t == 1) {
            int i,x; cin>>i>>x;
            a[--i] = --x;
        } else {
            int l,r,u; cin>>l>>r>>u;
            auto [x, y] = solve(--l, --r, --u);
            cout << 1+x << " " << 1+y << "\n";
        }
    }
}

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