Submission #541275

#	Time	Username	Problem	Language	Result	Execution time	Memory
541275		Tadiorn	Birthday gift (IZhO18_treearray)	C++14	0 / 100	34 ms	48328 KiB

treearray

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
#define MAXN 200010
#define LGN 18
using namespace std;

vector<int> a[MAXN];
int val[MAXN];
set<int> indeksi[MAXN];
set<int> indeksi2[MAXN];
int st[LGN][MAXN];
int in[MAXN], out[MAXN];
int T;

void dfs(int s, int p){
    in[s] = ++T;
    st[0][s] = p;
    for(auto x : a[s]){
        if(x != p){
            dfs(x, s);
        }
    }
    out[s] = ++T;
}

void init(int n){
    for(int lg = 1; lg < LGN; lg++){
        for(int i = 0; i < n; i++){
            st[lg][i] = st[lg-1][st[lg-1][i]];
        }
    }
}

bool UinV(int u, int v){ /// da li je cvor U u podstablu cvora V
    if(in[v] <= in[u] && out[u] <= out[v]) return true;
    return false;
}

int lca(int u, int v){
    if(UinV(u, v)) return v;
    if(UinV(v, u)) return u;
    int tr = u;
    for(int lg = LGN; lg >= 0; lg--)
        if(!UinV(v, st[lg][tr]))
            tr = st[lg][tr];
    return st[0][tr];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v; u--; v--;
        a[u].pb(v); a[v].pb(u);
    }
    dfs(0, 0);
    init(n);
    /*for(int i = 0; i < n; i++){
        cout << i+1 << ": ";
        for(int j = 0; j < 5; j++) cout << st[j][i]+1 << " ";
        cout << endl;
    }*/
    /*while(true){
        cout << "START" << endl;
        int u, v; cin >> u >> v; u--, v--;
        cout << lca(u, v) + 1 << endl;
    }*/
    for(int i = 0; i < m; i++){
        cin >> val[i]; val[i]--;
        indeksi2[val[i]].insert(i);
    }
    for(int i = 1; i < m; i++){
        indeksi[lca(val[i-1], val[i])].insert(i-1);
    }
    /*for(int i = 0; i < n; i++){
        cout << i+1 << ": ";
        for(auto x : indeksi[i]){
            cout << x + 1 << " ";
        } cout << endl;
    }*/
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int idx, v; cin >> idx >> v; idx--; v--;
            if(idx >= 1){
                indeksi[lca(val[idx-1], val[idx])].erase(idx-1);
                indeksi[lca(val[idx-1], v)].insert(idx-1);
            }
            if(idx < m-1){
                indeksi[lca(val[idx], val[idx+1])].erase(idx);
                indeksi[lca(v, val[idx+1])].insert(idx);
            }
            indeksi2[val[idx]].erase(idx);
            indeksi2[v].insert(idx);
            val[idx] = v;
            /*cout << "---" << endl;
            for(int i = 0; i < n; i++){
                cout << i+1 << ": ";
                for(auto x : indeksi[i]){
                    cout << x + 1 << " ";
                } cout << endl;
            }
            cout << "---" << endl;*/
        }
        else{
            int l, r, v; cin >> l >> r >> v; l--, v--, r--;
            auto it2 = indeksi2[v].lower_bound(l);
            if(it2 != indeksi2[v].end() && *it2 <= r){cout << *it2+1 << " " << *it2+1 << endl; continue;}
            auto it = indeksi[v].lower_bound(l);
            if(it == indeksi[v].end()) cout << "-1 -1" << endl;
            else if(*it + 1 <= r) cout << *it + 1 << " " << *it+2 << endl;
            else cout << "-1 -1" << endl;
        }
    }

    return 0;
}



/**
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1




*/

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