Submission #697836

#	Time	Username	Problem	Language	Result	Execution time	Memory
697836		vjudge1	Birthday gift (IZhO18_treearray)	C++17	30 / 100	4066 ms	5460 KiB

treearray

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

using namespace std;
const long long mod = (long long)1e9+7;
const int N = 200200;
int n, m, q, a[N], d[N], up[20][N];
vector<int> g[N];

void dfs(int v, int pr) {
	up[0][v] = pr;
	for(int i = 1; i < 19; i++){
		up[i][v] = up[i-1][up[i-1][v]];
	}
	d[v] = d[pr] + 1;
	for(int to : g[v]) {
		if(to == pr) continue;
		dfs(to, v);
	}
}

int lca(int u, int v) {
	if(d[u] < d[v]) {
		int temp = u;
		u = v;
		v = temp;
	}
	for(int i = 18; i >= 0; i--){
		if(d[u] - (1<<i) >= d[v]) {
			u = up[i][u];
		}
	}
	if(u == v) return u;
	for(int i = 18; i >= 0; i--){
		if(up[i][u] != up[i][v]) {
			u = up[i][u];
			v = up[i][v];
		}
	}
	return up[0][v];
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));
    cin>>n>>m>>q;
    for (int i = 1; i<n; i++) {
        int x, y;
        cin>>x>>y;
        g[x].pb(y); g[y].pb(x);
    }
    for (int i = 1; i<=m; i++) {
        cin>>a[i];
    }
    dfs(1, 1);
    while (q--) {
        int t;
        cin>>t;
        if (t == 1) {
            int pos, v;
            cin>>pos>>v;
            a[pos] = v;
        } else {
            int l, r, v;
            cin>>l>>r>>v;
            int curr = 0;
            bool flag = false;
			for (int x = l; x <= r; x++) {
				for (int y = x; y <= r; y++) {
					if (y == x) curr = a[y];
					else curr = lca(curr, a[y]);
					if (curr == v) {
						cout<<x<<' '<<y<<'\n';
						flag = true;
						break;
					}
				// 	if (!isPar(v, curr)) break;
				}
				if (flag) break;
			}
			if (!flag)
			    cout<<"-1 -1\n";
        }
    }
    return 0;
}

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