oj.uz

Submission #92484

# Submission time Handle Problem Language Result Execution time Memory
92484 2019-01-03T05:39:10 Z Nodir_Bobiev Birthday gift (IZhO18_treearray) C++14
0 / 100
 15 ms 14456 KB 
# include <iostream>
# include <vector>
# include <set>

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];
set < int > st[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);
	
	for(int i = 1; i < m;  i++)
		st[lca(a[i], a[i + 1])].insert(i);

	for(int i = 1; i <= m;  i++)
		st[a[i]].insert(i);
		
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, v;
			cin >> pos >> v;
			
			if(pos < m){
				st[lca(a[pos], a[pos + 1])].erase(pos);
				st[  lca(v, a[pos + 1])  ].insert(pos);
			}
			if(pos > 1){
				st[lca(a[pos], a[pos - 1])].erase(pos - 1);
				st[  lca(v, a[pos - 1])  ].insert(pos - 1);			
			}
			st[a[pos]].erase(pos);
			st[   v  ].insert(pos);
			a[pos] = v;
			}
		
		else{
			int l, r, v;
			cin >> l >> r >> v;
			auto lw = st[v].lower_bound(l);
			
			if(lw == st[v].end() || *lw > r)
				cout << -1 << ' ' << -1 << endl;
			
			else if(a[*lw] == v)
				cout << *lw << ' ' << *lw << endl;
			
			else if(*lw != r)
				cout << *lw << ' ' << *lw + 1 << endl; 
			
			else
				cout << -1 << ' ' << - 1 << 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 15 ms 14456 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 14 ms 14456 KB n=100
5 Incorrect 13 ms 14456 KB Jury has the answer but participant has not
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 15 ms 14456 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 14 ms 14456 KB n=100
5 Incorrect 13 ms 14456 KB Jury has the answer but participant has not
6 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 15 ms 14456 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 14 ms 14456 KB n=100
5 Incorrect 13 ms 14456 KB Jury has the answer but participant has not
6 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB n=5
2 Correct 15 ms 14456 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 14 ms 14456 KB n=100
5 Incorrect 13 ms 14456 KB Jury has the answer but participant has not
6 Halted 0 ms 0 KB -