oj.uz

Submission #1100566

# Submission time Handle Problem Language Result Execution time Memory
1100566 2024-10-14T09:09:07 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
0 / 100
 4 ms 17144 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int N = 100001;

using namespace std;

ll n, m, k, a, b, c, e, d[N], bg[N], p[N], sz[N], h[N], up[N][22], tin[N], lc, sum, sum1, ans, mx[N], tout[N];
set <ll> s[N], st[N];
vector <ll> g[N];

void dfs (ll v, ll pp){
	up[v][0] = pp;
	sz[v] = 1;
	for (int i = 1; i <= 21; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i] != pp){
			d[g[v][i]] = d[v] + 1;
			dfs (g[v][i], v);
		}
	}
}

ll lca (ll a, ll b){
	if (d[a] < d[b]){
		swap (a, b);
	}
	ll c = abs (d[a] - d[b]);
	for (int i = 21; i >= 0; i--){
		if ((c >> i) & 1){
			a = up[a][i];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = 21; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb (a);
	}
	for (int i = 1; i <= m; i++){
		cin >> p[i];
	}
	dfs (1, 0);
	for (int i = 1; i < m; i++){
		st[p[i]].insert (i);
		s[lca (p[i], p[i + 1])].insert (i);
	}
	while (k--){
		cin >> a >> b >> c;
		if (a == 1){
			st[p[b]].erase (b);
			if (b != 1)s[lca (p[b], p[b - 1])].erase (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].erase (b);
			p[b] = c;
			st[p[b]].insert(b);
			if (b != 1)s[lca (p[b], p[b - 1])].insert (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].insert (b);
		}
		else{
			cin >> e;
			if (s[e].size() && *s[e].lower_bound(b) < c && *s[e].lower_bound(b) >= b){
				lc = *s[e].lower_bound(b);
				cout << lc << ' ' << lc + 1 << '\n';
			}
			else if (st[e].size() && *st[e].lower_bound(b) <= c && *st[e].lower_bound(b) >= b){
				cout << *st[e].lower_bound(b) << ' ' << *st[e].lower_bound (b) << '\n';
			}
			else{
				cout << "-1 -1\n";
			}
		}
	}
}

Compilation message

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB n=5
2 Correct 3 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 4 ms 16976 KB n=100
5 Correct 3 ms 17140 KB n=100
6 Correct 4 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 17144 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 17144 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 4 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 16976 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Incorrect 3 ms 16976 KB Jury has the answer but participant has not
18 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB n=5
2 Correct 3 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 4 ms 16976 KB n=100
5 Correct 3 ms 17140 KB n=100
6 Correct 4 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 17144 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 17144 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 4 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 16976 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Incorrect 3 ms 16976 KB Jury has the answer but participant has not
18 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB n=5
2 Correct 3 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 4 ms 16976 KB n=100
5 Correct 3 ms 17140 KB n=100
6 Correct 4 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 17144 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 17144 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 4 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 16976 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Incorrect 3 ms 16976 KB Jury has the answer but participant has not
18 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB n=5
2 Correct 3 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 4 ms 16976 KB n=100
5 Correct 3 ms 17140 KB n=100
6 Correct 4 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 17144 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 17144 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 4 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 16976 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Incorrect 3 ms 16976 KB Jury has the answer but participant has not
18 Halted 0 ms 0 KB -