Submission #1138858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138858		Skymagic	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4093 ms	33276 KiB

treearray

/********************
 * what  the  sigma *
 ********************/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define pb push_back
const ll mod = 1e9+7,maxn=200005;
const ll INF=(ll)9e18;
ve<int> ed[maxn];
int pa[maxn][20];
int dep[maxn];
void dfs(int u,int par) {
    pa[u][0]=par;
    for (int i=1;i<20;i++) {
        pa[u][i]=pa[pa[u][i-1]][i-1];
    }
    dep[u]=dep[par]+1;
    for (auto i:ed[u]) {
        if (i==par) continue;
        dfs(i,u);
    }
}
int lift(int u,int dist) {
    for (int i=0;i<20;i++) {
        if ((1<<i)&dist) {
            u=pa[u][i];
        }
    }
    return u;
}
signed main() {
    lgm;
    int n,m,q;
    cin >> n >> m >> q;
    int x,y,z;
    for (int i=0;i<n-1;i++) {
        cin >> x >> y;
        ed[x].pb(y);
        ed[y].pb(x);
    }
    dfs(1,1);
    ve<int> a(m+1);
    for (int i=1;i<=m;i++) {
        cin >> a[i];
    }
    while (q--) {
        cin >> x;
        if (x==1) {
            cin >> x >> y;
            a[x]=y;
        } else {
            cin >> x >> y >> z;
            int cur=0,st=0,en=0;
            bool yes=0;
            for (int i=x;i<=y;i++) {
                if (a[i]==z) {
                    yes=1;
                    st=en=i;
                    break;
                }
                if (dep[z]>=dep[a[i]]) {cur=0;continue;}
                int v=lift(a[i],dep[a[i]]-dep[z]-1);
                if (pa[v][0]==z) {
                    if (cur==0) cur=v,st=i,en=i;
                    else if (v!=cur) {
                        yes=1;
                        en=i;
                        break;
                    }
                } else {
                    cur=0;
                }
            }
            if (yes) {
                cout << st SP en << '\n';
            } else {
                cout << "-1 -1\n";
            }
        }
    }
}

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