Submission #1162856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162856		SulA	Birthday gift (IZhO18_treearray)	C++20	0 / 100	0 ms	836 KiB

treearray

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

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

void dfs(int u = 0, int p = -1) {
    in[u] = t++;
    sub[u] = {u};
    lca[u][u] = u;
    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);
        for (int x : sub[v]) {
            for (int y : sub[u]) {
                lca[x][y] = lca[y][x] = u;
            }
        }
        for (int x : sub[v]) sub[u].push_back(x);
    }
    out[u] = t++;
}

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

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 (subtree.empty()) { last = i+1; continue; }
            int L = subtree[0];
            for (int x : subtree) L = lca[L][x];
            if (L == u) return {last, i-1};
            last = i+1;
        }
    }
    if (subtree.empty()) return {-2, -2};
    int L = subtree[0];
    for (int x : subtree) L = lca[L][x];
    if (L == 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 < n; i++) {
//        for (int j = 0; j < n; j++) {
//            cout << i+1 << " " << j+1 << " " << 1+lca[i][j] << "\n";
//        }
//    }
    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: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44