Submission #1139311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139311		Skymagic	Birthday gift (IZhO18_treearray)	C++17	0 / 100	12 ms	23876 KiB

treearray

/********************
 * what  the  sigma *
 ********************/
#include <iostream>
#include <vector>
#include <map>
#include <set>
#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<tuple<int,int,int>,pii,pii>
#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];
int a[maxn];
set<int> st[maxn],st2[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;
}
int lca(int u,int v) {
    if (dep[u]<dep[v]) swap(u,v);
    lift(u,dep[u]-dep[v]);
    if (u==v) return u;
    for (int i=19;i>=0;i--) {
        if (pa[u][i]!=pa[v][i]) {
            u=pa[u][i];
            v=pa[v][i];
        }
    }
    return pa[u][0];
}
bool isdescendant(int u,int v) {
    return lca(u,v)==v;
}
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);
    for (int i=1;i<=m;i++) {
        cin >> a[i];
    }
    for (int i=1;i<=m;i++) {
        if (i<m) {
            st[lca(a[i],a[i+1])].insert(i);
        }
        st2[a[i]].insert(i);
    }
    while (q--) {
        cin >> x;
        if (x==1) {
            cin >> x >> y;
            if (x<m) {
                st[lca(a[x],a[x+1])].erase(x);
            }
            if (x>1) {
                st[lca(a[x],a[x-1])].erase(x-1);
            }
            st2[a[x]].erase(x);
            a[x]=y;
            st2[a[x]].insert(x);
            if (x<m) {
                st[lca(a[x],a[x+1])].insert(x);
            }
            if (x>1) {
                st[lca(a[x],a[x-1])].insert(x-1);
            }
        } else {
            cin >> x >> y >> z;
            if (x==y) {
                if (a[x]==z) {
                    cout << x SP x << '\n';
                } else {
                    cout << "-1 -1\n";
                }
                continue;
            }
            auto a=lower_bound(be(st[z]),x),b=lower_bound(be(st2[z]),x);
            if (a!=st[z].end()&&(*a)<y) {
                cout << *a SP (*a)+1 << '\n';
            } else if (b!=st2[z].end()&&(*b)<=y) {
                cout << *b SP *b << '\n';
            } else {
                cout << "-1 -1\n";
            }
        }
    }
}

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