Submission #217860

#	Time	Username	Problem	Language	Result	Execution time	Memory
217860		socho	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1762 ms	77024 KiB

treearray

#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double
// #define int long long
// int MOD = 1000 * 1000 * 1000 + 7;
// int MOD = 998244353;

int n, m, q;
const int MXN = 200005, MXK = 20;
vector<int> adj[MXN];

int par[MXN][MXK];
int depth[MXN];

void dfs_par(int node, int last, int dep) {
	depth[node] = dep;
	par[node][0] = last;
	for (int i=1; i<MXK; i++) {
		int op = par[node][i-1];
		if (op != -1) {
			par[node][i] = par[op][i-1];
		}
	}
	for (int i=0; i<adj[node].size(); i++) {
		int o = adj[node][i];
		if (o == last) continue;
		dfs_par(o, node, dep+1);
	}
}

int kth_parent(int n, int k) {
	for (int i=0; i<MXK; i++) {
		if (k & (1 << i)) {
			n = par[n][i];
		}
	}
	return n;
}

int lca(int a, int b) {
	if (depth[a] > depth[b]) swap(a, b);
	b = kth_parent(b, depth[b] - depth[a]);
	if (a == b) return a;
	for (int i=MXK-1; i>=0; i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}


signed main() {
	
	for (int i=0; i<MXN; i++) for (int j=0; j<MXK; j++) par[i][j] = -1;
	
	cin >> n >> m >> q;
	for (int i=0; i<n-1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs_par(1, -1, 0);
	
	set<int> occ[n+1], loc[n+1];
	
	int arr[m];
	for (int i=0; i<m; i++) {
		cin >> arr[i];
		occ[arr[i]].insert(i);
	}
	
	int imm_lca[m-1];
	for (int i=0; i<m-1; i++) {
		imm_lca[i] = lca(arr[i], arr[i+1]);
		loc[imm_lca[i]].insert(i);
	}
	
	for (int i=0; i<q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			int pos, to;
			cin >> pos >> to;
			pos--;
			int f = arr[pos];
			occ[f].erase(pos);
			occ[to].insert(pos);
			arr[pos] = to;
			if (pos > 0) {
				// can try before
				int pr = imm_lca[pos-1];
				loc[pr].erase(pos-1);
				imm_lca[pos-1] = lca(arr[pos-1], to);
				loc[imm_lca[pos-1]].insert(pos-1);
			}
			if (pos < m-1) {
				// can try after
				int pr = imm_lca[pos];
				loc[pr].erase(pos);
				imm_lca[pos] = lca(to, arr[pos+1]);
				loc[imm_lca[pos]].insert(pos);
			}
			
		}
		else {
			int l, r, w;
			cin >> l >> r >> w;
			l--; r--;
			set<int>::iterator x = occ[w].lower_bound(l);
			if (x == occ[w].end() || *x > r) {
				// cant use same one
				x = loc[w].lower_bound(l);
				if (x == loc[w].end() || *x >= r) {
					cout << -1 << ' ' << -1 << endl;
				}
				else {
					int f = *x;
					cout << f+1 << ' ' << f+2 << endl;
				}
			}
			else {
				int f = *x;
				cout << f+1 << ' ' << f+1 << endl;
			}
		}
	}
	
}

Compilation message (stderr)

treearray.cpp: In function 'void dfs_par(int, int, int)':
treearray.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~

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