제출 #1156841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156841		andrewp	Birthday gift (IZhO18_treearray)	C++20	56 / 100	82 ms	676 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N=2005;

int n, m, q, up[N][12], a[N], dep[N];
vector<int> g[N];

void dfs(int x, int par) {
    up[x][0]=par;
    dep[x]=dep[par]+1;
    for (int i=1; i<12; i++)
        up[x][i]=up[up[x][i-1]][i-1];
    for (int u:g[x])
        if (u!=par)
            dfs(u, x);
}

int raise(int x, int y) {
    int z=0;
    while (y) {
        if (y&1)
            x=up[x][z];
        z++;
        y>>=1;
    }
    return x;
}

int lca(int a, int b) {
    if (dep[a]>dep[b])
        swap(a, b);
    int x=dep[b]-dep[a];
    b=raise(b, x);
    if (a==b)
        return a;
    for (int i=11; i>=0; i--) {
        if (up[a][i]!=up[b][i]) {
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

int32_t main () {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m >> q;
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);
    for (int i=1; i<=m; i++)
        cin >> a[i];
    while (q--) {
        int tp;
        cin >> tp;
        if (tp==1) {
            int pos, v;
            cin >> pos >> v;
            a[pos]=v;
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            int x=0;
            for (int i=l; i<=r; i++) {
                if (a[i]==v)
                    x=i;
            }
            if (x) {
                cout << x << ' ' << x << '\n';
                continue;
            }
            for (int i=l; i<r; i++) {
                if (lca(a[i], a[i+1])==v)
                    x=i;
            }
            if (x)
                cout << x << ' ' << x+1 << '\n';
            else
                cout << -1 << ' ' << -1 << '\n';
        }
    }
    return 0;
}

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