Submission #1242153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242153		Amaarsaa	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	5184 KiB

treearray

#include<bits/stdc++.h>

using namespace std;
using ll =long long;
const ll N = 2e5 + 2;

vector < ll > adj[N];
ll anc[20][N], tin[N], tout[N], timer = 0;
ll a[N];

bool is_ancestor(ll x, ll y) {
    if ( tin[x] <= tin[y] && tout[y] <= tout[x]) return 1;
    return 0;
}

ll LCA(ll x, ll y) {
    if ( is_ancestor(x, y)) return x;
    if ( is_ancestor(y, x)) return y;

    for (int i = 18; i >= 0; i --) {
        if ( !is_ancestor(anc[i][x], y)) x =anc[i][x];
    }

    return anc[0][x];
}



void Go(ll node, ll par) {
    timer ++;
    anc[0][node] = par;
    tin[node] = timer;
    for (int i = 1; i <= 18; i ++) anc[i][node] = anc[i - 1][anc[i - 1][node]];
    for (ll nxt : adj[node]) {
        if ( nxt == par) continue;
        Go(nxt, node);
    }
    timer ++;
    tout[node] = timer;
}

ll T[4 * N];

void Build(ll p, ll lo, ll hi) {
    if ( lo == hi) {
        T[p] = a[lo];
        return ;
    }
    ll mid = (lo + hi)/2;

    Build(2 * p, lo, mid);
    Build(2 * p + 1, mid + 1, hi);

    T[p]= LCA(T[2 * p], T[2 * p + 1]);
    return ;
}

ll ans_lo , ans_hi;
ll Find(ll p, ll lo, ll hi, ll l, ll r, ll x) {
    if ( lo > r || l > hi) return -1;
    if ( l <= lo && hi <=r ) {
        if ( T[p] == x) {
            ans_lo = max(lo, l);
            ans_hi = min(hi, r);
        }
        return T[p];
    }
    ll mid = (lo + hi)/2, lef, rig;
    lef =Find(2 * p, lo, mid, l, r, x);
    rig =Find(2 * p + 1, mid + 1, hi, l, r, x);

    if ( lef == -1) return rig;
    if ( rig == -1) return lef;
    lef = LCA(lef, rig);
    if ( lef == x) {
        ans_lo = max(lo, l);
        ans_hi = min(hi, r);
    }
    return lef;
}

void Update(ll p, ll lo, ll hi , ll x, ll y){
    if ( lo == hi) {
        T[p] = y;
        return ;
    }

    ll mid = (lo + hi)/2;

    if ( x <= mid) Update(2 * p, lo, mid, x, y);
    else Update(2 * p + 1, mid + 1, hi, x, y);

    T[p] = LCA(T[2 * p], T[2 * p + 1]);
}

int main() {
    ll n, m, r, s, t,q, i, ans, lo, hi, mx_ind, mx, x, y, j;

    cin >> n >> m >> q;

    for (i = 1; i < n; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    Go(1, 1);

    for (i = 1; i <= m; i ++) {
        cin >> a[i];
    }

    Build(1, 1, m);

    cout<< LCA(3, 2) << endl;
    while (q --) {
        cin >> x;
        if ( x == 2) {
            cin >> lo >> hi >> x;
            ans_lo = ans_hi = -1;
            r = Find(1, 1, m, lo, hi, x);
            cout << r << " " << ans_lo << " " << ans_hi << endl;
        }
        else {
            cin >> x >> y;
            Update(1, 1, m, x, y);
        }
    }
}

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