Submission #316719

#	Time	Username	Problem	Language	Result	Execution time	Memory
316719		vitkishloh228	Birthday gift (IZhO18_treearray)	C++14	0 / 100	1 ms	512 KiB

treearray

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
const int logn = 20;
vector<vector<int>> g, up;
vector<int> used, tin, tout;
int timer = 0;
void dfs(int v) {
    used[v] = 1;
    tin[v] = timer++;
    for (int i = 1; i < logn; ++i) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for (auto u : g[v]) {
        if (!used[u]) {
            up[0][u] = v;
            dfs(u);
        }
    }
    tout[v] = timer;
}
bool par(int a, int b) {
    return (tin[a] <= tin[b] && tin[b] < tout[a]);
}
int lca(int a, int b) {
    if (par(a, b)) return a;
    if (par(b, a)) return b;
    for (int i = logn - 1; i >= 0; i--) {
        if (!par(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    g.resize(n);
    up = vector<vector<int>>(logn, vector<int>(n));
    tin.resize(n);
    tout.resize(n);
    used.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0);
    vector<set<int>> S0(n), S1(n);
    vector<int> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        --a[i];
    }
    for (int i = 0; i < m - 1; ++i) {
        S1[lca(a[i], a[i + 1])].insert(a[i]);
    }
    for (int i = 0; i < m; ++i) {
        S0[a[i]].insert(i);
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, v;
            cin >> pos >> v;
            --pos;
            S0[a[pos]].erase(a[pos]);
            if (pos != m - 1) {
                S1[lca(a[pos], a[pos + 1])].erase(pos);
            }
            if (pos) {
                S1[lca(a[pos - 1], a[pos])].erase(pos - 1);
            }
            a[pos] = v;
            S0[a[pos]].insert(a[pos]);
            if (pos != m - 1) {
                S1[lca(a[pos], a[pos + 1])].insert(pos);
            }
            if (pos) {
                S1[lca(a[pos - 1], a[pos])].insert(pos - 1);
            }
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            --l, --r;
            auto it = *S0[v].lower_bound(l);
            if (it <= r) {
                cout << it + 1 << ' ' << it + 1 << '\n';
                continue;
            }
            auto it1 = *S1[v].lower_bound(l);
            if (it1 < r) {
                cout << it1 + 1 << ' ' << it1 + 2 << '\n';
                continue;
            }
            cout << "-1 -1\n";
        }
    }
}

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