Submission #340631

#	Time	Username	Problem	Language	Result	Execution time	Memory
340631		Dilshod_Imomov	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4080 ms	130688 KiB

treearray

# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define int long long
# define fi first
# define se second
 
using namespace std;
 
const int N = 2e6 + 7;
const int mod = 1e9 + 7;

int a[N], up[N][40], tin[N], tout[N], timer = 1, lg, x, y;
vector < int > adj[N];

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

bool is_upper( int a, int b ) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int LCA( int a, int b ) {
    if ( is_upper( a, b ) ) {
        return a;
    }
    if ( is_upper( b, a ) ) {
        return b;
    }
    for ( int i = lg; i >= 0; i-- ) {
        if ( !is_upper( up[a][i], b ) ) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

void rec( int l, int r, int v ) {
    if ( l > r ) {
        return;
    }
    int lca = a[l];
    for ( int i = l; i <= r; i++ ) {
        if ( !is_upper( v, a[i] ) ) {
            rec( i + 1, r, v );
            return;
        }
        lca = LCA( lca, a[i] );
        if ( lca == v ) {
            x = l;
            y = i;
            return;
        }
    }
}

int32_t main() {
    speed;
    int n, m, q;
    cin >> n >> m >> q;
    lg = log2(n) + 1;
    for ( int i = 1; i < n; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs( 1, 1 );
    for ( int i = 1; i <= m; i++ ) {
        cin >> a[i];
    }
    for ( int i = 1; i <= q; i++ ) {
        int t;
        cin >> t;
        if ( t == 1 ) {
            int pos, val;
            cin >> pos >> val;
            a[pos] = val;
        }
        else {
            int l, r, v;
            cin >> l >> r >> v;
            x = y = -1;
            rec( l, r, v );
            cout << x << ' ' << y << '\n';
        }
    }
}

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