Submission #1208206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208206		andrejikus	Birthday gift (IZhO18_treearray)	C++20	56 / 100	535 ms	96036 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 2e5 + 3;
const int logn = 20;
int tin[N], tout[N], a[N], timer = 0;
set<int> S[N], T[N];
vector<int> adj[N];
int up[N][logn];

void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    for (int j = 1; j < logn; j++)
        up[u][j] = up[up[u][j-1]][j-1];
    for (auto x : adj[u]) if (x != p) {
        dfs(x, u);
    }
    tout[u] = timer;
}

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

int get_lca(int u, int v) {
    if (IsAncestor(u, v)) return u;
    if (IsAncestor(v, u)) return v;

    for (int j = logn-1; j >= 0; j--) {
        if (up[u][j] != 0 && !IsAncestor(up[u][j], v))
            u = up[u][j];
    }
    return up[u][0];
}

void solve() {
    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(1, 0);
    for (int i = 1; i <= m; i++) cin >> a[i], S[a[i]].insert(i);
    for (int i = 1; i <= m-1; i++) T[get_lca(a[i], a[i+1])].insert(i);
    for (int i = 1; i <= n; i++) T[i].insert(1e9), S[i].insert(1e9);

    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int i, v; cin >> i >> v;
            S[a[i]].erase(i);
            if (i+1 <= n)
                T[get_lca(a[i], a[i+1])].erase(i);
            if (i-1 >= 1)
                T[get_lca(a[i-1], a[i])].erase(i-1);
            a[i] = v;
            S[a[i]].insert(i);
            if (i+1 <= n)
                T[get_lca(a[i], a[i+1])].insert(i);
            if (i-1 >= 1)
                T[get_lca(a[i-1], a[i])].insert(i-1);
        } else {
            int l, r, v; cin >> l >> r >> v;
            int d = *S[v].lower_bound(l);
            if (d <= r) {
                cout << d << " " << d << "\n"; continue;
            }
            int e = *T[v].lower_bound(l);
            if (e <= r-1) {
                cout << e << " " << e+1 << "\n"; continue;
            }
            cout << "-1 -1\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
	int t=1; //cin >> t;
	while (t--) {
        solve();
	}
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
2 3 4 5
2 1 3 1
1 3 5

5 4 4
1 2
3 1
3 4
5 3
4 5 5 3
2 1 3 1
2 3 4 5
2 1 3 1
1 3 5
*/

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