제출 #92366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92366		Nodir_Bobiev	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4078 ms	22492 KiB

treearray

# include <iostream>
# include <vector>

using namespace std;

const int N = 2e5 + 100;

int n, m, q;
int p[N];
int g[N] = {-1};
int a[N];
vector < int > gr[N];

void dfs(int v, int f)
{
	g[v] = g[f] + 1;
	p[v] = f;
	for(auto to: gr[v])
		if(to != f)
			dfs(to, v);
}

int lca(int v, int u)
{
	if(g[v] > g[u]) return lca(p[v], u);
	if(g[v] < g[u]) return lca(v, p[u]);
	if(v != u) return lca(p[v], u);
	return v;
}

int main()
{
	
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		gr[v].push_back(u);
		gr[u].push_back(v);
	}
	
	for (int i = 1; i <= m; i++)
		cin >> a[i];
	
	dfs(1, 0);
		
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, v;
			cin >> pos >> v;
			a[pos] = v;
		}
		else{
			int l, r, v, l1 = -1, r1 = -1;
			cin >> l >> r >> v;
			//cout << l << ' ' << r << ' ' << v << endl;
			for (int x = l; x <= r; x++){
				//cout << '\t' << lca(a[x], a[x + 1]) << endl;
				if(x != r && lca(a[x], a[x + 1]) == v){
					l1 = x; r1 = x + 1;
					break;
				}
				else if(a[x] == v){
					l1 = x; r1 = x;
					break;
				}
			}
			cout << l1 << ' ' << r1 << endl;
		}
	}
}

/*

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: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44