Submission #1114062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114062		vjudge1	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4049 ms	56772 KiB

treearray

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50,Q = 2e5+50;


vi edges[N];
int tin[N],tout[N];
int A[N],B[N];
int timer = 1;
int up[N][20];

void dfs(int node,int p) {
    tin[node] = timer++;
    up[node][0] = p;
    for (auto it : edges[node]) {
        if (it != p) dfs(it,node);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i = 19;i>=0;i--) if (!anc(up[a][i],b)) a = up[a][i];
    return up[a][0];
}

void solve() { 
    int n,m,q;
    cin >> n >> m >> q;
    for (int i=1;i<=n-1;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1,1);
    for (int i = 1;i<=m;i++) {
        cin >> B[i];
    }
    for (int i=1;i<20;i++) {
        for (int j = 1;j<=n;j++) up[j][i] = up[up[j][i-1]][i-1];
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int p,v;
            cin >> p >> v;
            A[p] = tin[v], B[p] = v;
        }
        else {
            int l,r,v;
            cin >> l >> r >> v;
            int runner = 0;
            int start = 0;
            bool fl = 0;
            for (int j = l;j<=r;j++) {
                if (!anc(v,B[j])) {
                    runner = 0;
                    continue;
                }
                if (!runner) runner = B[j],start = j;
                else runner = lca(runner,B[j]);
                if (runner == v) {
                    cout << start << " " << j << '\n';
                    fl = 1;
                    break;
                }
            }
            if (fl) continue;
            cout << -1 << " " << -1 << '\n';   
        }
    }
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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