Submission #1165044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165044		AliMark71	Birthday gift (IZhO18_treearray)	C++20	0 / 100	0 ms	324 KiB

treearray

//
//  main.cpp
//  GeneralCompetitiveProgramming
//
//  Created by Ali AlSalman on 12/07/2023.
//

#include <bits/stdc++.h>

//#define INTERACTIVE
//#define TESTCASES

#ifndef INTERACTIVE
#define endl '\n'
#endif

template<typename T>
using vec = std::vector<T>;
using namespace std;

unordered_map<int, set<int>> ind_seq;
unordered_map<int, set<int>> ind_slc;
vec<vec<int>> adj;

vec<vec<int>> st(19);
vec<int> dep;

void root(int u = 0, int p = -1, int d = 0) {
    st[0][u] = p;
    dep[u] = d;
    for (auto c : adj[u]) if (c != p) {
        root(c, u, d + 1);
    }
}

void init_bin_lift() {
    for (int k = 1; k < st.size(); k++) for (int i = 0; i < st.front().size(); i++) if (st[k - 1][i] != -1) {
        st[k][i] = st[k - 1][st[k - 1][i]];
    }
}

int lca(int a, int b) {
    if (dep[b] < dep[a]) swap(a, b);
    int climb = dep[b] - dep[a];
    for (int i = 0; i < 19; i++) if ((1<<i)&climb) {
        b = st[i][b];
    }
    
    if (a == b) return a;
    for (int i = 18; 0 <= i; i--) {
        if (st[i][a] != st[i][b]) {
            a = st[i][a];
            b = st[i][b];
        }
    }
    
    return st[0][a];
}

void solve() {
    int n, m, q;
    cin>>n>>m>>q;
    adj.resize(n);
    for (int i = n - 1; i--;) {
        int a, b;
        cin>>a>>b; a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    vec<int> seq(m);
    for (int i = 0; i < m; i++) {
        cin>>seq[i];
        ind_seq[--seq[i]].insert(i);
    }
    
    fill(st.begin(), st.end(), vec<int>(n, -1));
    dep.resize(n);
    root();
    init_bin_lift();
    
    vec<int> slc(m - 1);
    for (int i = 0; i < slc.size(); i++){
        slc[i] = lca(seq[i], seq[i + 1]);
        ind_slc[slc[i]].insert(i);
    }
    
    
    while (q--) {
        int t;
        cin>>t;
        if (t == 1) {
            int i, v;
            cin>>i>>v; i--; v--;
            ind_seq[seq[i]].erase(i);
            ind_seq[seq[i] = v].insert(i);
            
            if (i < m - 1) {
                ind_slc[slc[i]].erase(i);
                ind_slc[slc[i] = lca(seq[i], seq[i + 1])].insert(i);
            }
            
            if (0 < i) {
                ind_slc[slc[i - 1]].erase(i - 1);
                ind_slc[slc[i - 1] = lca(seq[i - 1], seq[i])].insert(i);
            }
        } else {
            int l, r, v;
            cin>>l>>r>>v; l--; r--; v--;
            
            auto seq_lit = ind_seq[v].lower_bound(l);
            auto seq_uit = ind_seq[v].upper_bound(r);
            if (seq_lit != seq_uit) {
                cout<<*seq_lit + 1<<' '<<*seq_lit + 1<<endl;
                continue;
            }
            
            auto slc_lit = ind_slc[v].lower_bound(l);
            auto slc_uit = ind_slc[v].upper_bound(r);
            if (slc_lit != slc_uit) {
                cout<<*slc_lit + 1<<' '<<*slc_lit + 2<<endl;
                continue;
            }
            
            cout<<"-1 -1"<<endl;
        }
    }
}

int main() {
#ifndef INTERACTIVE
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
    
    int t = 1;
#ifdef TESTCASES
    cin>>t;
#endif
    while (t--) solve();
}

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