Submission #219810

#	Time	Username	Problem	Language	Result	Execution time	Memory
219810		infinite_iq	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1369 ms	84216 KiB

treearray

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 400
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 4e18;
const ld pai=acos(-1);
int n , m , q;
vi v[200009];
int w[200009] , dp[200009][20] , a[200009];
set<int>s[200009],t[200009];
void dfs(int node,int p){
        dp[node][0]=p;
        w[node]=w[p]+1;
        for ( auto u : v[node]){
                if ( u == p ) C ;
                dfs ( u, node ) ;
        }
}
void build () {
        dfs ( 0,0 );
        for ( int j =1 ;j < 20 ;j ++ ) {
                for ( int i =0 ;i < n ;i ++ ) {
                        dp[i][j] = dp[dp[i][j-1]][j-1];
                }
        }
}
int lca(int a,int b ){
        if ( w[a] < w[b] ) swap ( a , b );
        int l = w[a] - w[b];
        for ( int i =0 ;i <20 ;i ++ ){
                if ( ( l & ( 1<<i ) ) ) a= dp[a][i];
        }
        if ( a == b ) return a ;
        for ( int i = 19 ; i>=0 ;i -- ){
                if ( dp[a][i] != dp[b][i] ) {
                        a=dp[a][i];
                        b=dp[b][i];
                }
        }
        return dp[a][0];
}
int main (){
        fast;
        cin >> n >> m >> q ;
        for ( int i =0 ;i < n-1 ;i ++ ) {
                int a,b;
                cin >> a >> b ;
                a -- , b -- ;
                v[a].pb ( b );
                v[b].pb ( a );
        }
        build();
        for ( int i =0 ;i < m ;i ++ ) {
                cin >> a[i];
                a[i] -- ;
                s[a[i]].ins ( i ) ;
                if ( i ) {
                        t[lca(a[i],a[i-1])].ins(i);
                }
        }
        while ( q -- ) {
                int ty ;
                cin >> ty ;
                if ( ty == 1 ){
                        int pos , id ;
                        cin >> pos >> id ;
                        pos -- , id -- ;
                        s [ a[pos] ] .era(pos);
                        s [ id     ] .ins(pos);
                        if ( pos ) t[lca(a[pos],a[pos-1])].era(pos);
                        if ( pos<m-1) t[lca(a[pos],a[pos+1])].era(pos+1);
                        a[pos]=id;
                        if ( pos ) t[lca(a[pos],a[pos-1])].ins(pos);
                        if ( pos<m-1) t[lca(a[pos],a[pos+1])].ins(pos+1);
                }
                if ( ty == 2 ){
                        int l ,r , node;
                        cin >> l >> r >> node;
                        l -- ,r -- , node -- ;
                        auto it = s[node].lb(l);
                        if ( it != s[node].end() && *it<=r) {
                                cout << *it+1 <<" " << *it+1 << endl;
                                C;
                        }
                        it = t[node].ub(l);
                        if ( it !=t[node].end() && *it<=r ) {
                                cout << *it <<" "<<*it+1<<endl;
                                C;
                        }
                        cout << -1 <<" "<< -1 << endl;

                }
        }
}

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