oj.uz

Submission #92812

# Submission time Handle Problem Language Result Execution time Memory
92812 2019-01-05T04:44:01 Z Nodir_Bobiev Birthday gift (IZhO18_treearray) C++17
0 / 100
 14 ms 14472 KB 
# include <iostream>
# include <set>
# include <vector>

using namespace std;

const long long N = 2e5 + 100;

int n, m, q;
int g[N], p[N], a[N];
vector < int > gr[N];
set < int > st[N];

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

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


int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++){
		int a, b; cin >> a >> b;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	dfs(1, 0);
	
	for (int i = 1; i <= m; i++)
		cin >> a[i];
		
	for (int i = 1; i <= m; i++){
		st[a[i]].insert(i);
		if(i != m)
			st[lca(a[i], a[i + 1])].insert(i);
	}
	
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int pos, val;
			cin >> pos >> val;
			st[a[pos]].erase(pos);
			st[val].insert(pos);
			if(pos != 1){
				st[lca(a[pos], a[pos - 1])].erase(pos - 1);
				st[lca(  val , a[pos - 1])].insert(pos - 1);
			}
			if(pos != m){
				st[lca(a[pos], a[pos + 1])].erase(pos);
				st[lca(  val , a[pos + 1])].insert(pos);
			}
			a[pos] = val;
		}
		else{
			int l, r, u;
			cin >> l >> r >> u;
			set < int > :: iterator pos = st[u].lower_bound(l);
			
			if(pos == st[u].end() || *pos > r)
				cout << -1 <<' '<< -1 <<endl;
			
			else if(a[*pos] == u)
				cout << *pos << ' ' << *pos << endl;
			
			else if(*pos < r)
				cout << *pos << ' ' << *pos + 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 12 ms 14456 KB n=5
2 Correct 14 ms 14472 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 12 ms 14456 KB n=100
5 Incorrect 12 ms 14428 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 12 ms 14456 KB n=5
2 Correct 14 ms 14472 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 12 ms 14456 KB n=100
5 Incorrect 12 ms 14428 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 12 ms 14456 KB n=5
2 Correct 14 ms 14472 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 12 ms 14456 KB n=100
5 Incorrect 12 ms 14428 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 12 ms 14456 KB n=5
2 Correct 14 ms 14472 KB n=100
3 Correct 12 ms 14456 KB n=100
4 Correct 12 ms 14456 KB n=100
5 Incorrect 12 ms 14428 KB Jury has the answer but participant has not
6 Halted 0 ms 0 KB -