Submission #445722

#	Time	Username	Problem	Language	Result	Execution time	Memory
445722		zxcvbnm	Birthday gift (IZhO18_treearray)	C++14	0 / 100	4 ms	6604 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 2e5 + 5;
int L = 20, timer = 0;
vector<int> adj[maxN], tin(maxN), tout(maxN);
int up[maxN][21];
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];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    L = ceil(log2(n));
    for(int i = 0; i < n-1; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    vector<int> seq(m);
    set<array<int, 3>> can;
    auto rem = [&](int x, int l, int r) {
        can.erase({x, l, r});
    };
    auto add = [&](int x, int l, int r) {
        can.insert({x, l, r});
    };

    for(int i = 0; i < m; i++) {
        cin >> seq[i];
    }

    dfs(1, 1);

    for(int pos = 0; pos < m; pos++) {
        add(seq[pos], pos+1, pos+1);
        if (pos != 0) {
            add(lca(seq[pos], seq[pos-1]), pos-1+1, pos+1);
        } else if (pos != m-1) {
            add(lca(seq[pos], seq[pos+1]), pos+1, pos+1+1);
        }
    }


    while(q--) {
        int type;
        cin >> type;
//        for(auto i : can) {
//            cout << i[0] << " " << i[1] << " " << i[2] << "\n";
//        }

        if (type == 1) {
            int pos, v;
            cin >> pos >> v;
            pos--;
            rem(seq[pos], pos+1, pos+1);
            if (pos != 0) {
                rem(lca(seq[pos], seq[pos-1]), pos-1+1, pos+1);
            } else if (pos != m-1) {
                rem(lca(seq[pos], seq[pos+1]), pos+1, pos+1+1);
            }

            seq[pos] = v;
            add(seq[pos], pos+1, pos+1);
            if (pos != 0) {
                add(lca(seq[pos], seq[pos-1]), pos-1+1, pos+1);
            } else if (pos != m-1) {
                add(lca(seq[pos], seq[pos+1]), pos+1, pos+1+1);
            }
        } else if (type == 2) {
            int l, r, v;
            cin >> l >> r >> v;
            auto it = can.lower_bound({v, l, l});
            if (it != can.end() && (*it)[0] == v && (*it)[1] >= l && (*it)[2] <= r) {
                cout << (*it)[1] << " " << (*it)[2] << "\n";
            } else {
                cout << "-1 -1\n";
            }
        }
    }
    return 0;
}

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