#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+1]].insert(pos+1);
}
}
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
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++) {
~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
n=5 |
| 2 |
Correct |
16 ms |
20736 KB |
n=100 |
| 3 |
Correct |
50 ms |
20600 KB |
n=100 |
| 4 |
Correct |
47 ms |
20728 KB |
n=100 |
| 5 |
Correct |
16 ms |
20736 KB |
n=100 |
| 6 |
Correct |
16 ms |
20736 KB |
n=100 |
| 7 |
Correct |
16 ms |
20608 KB |
n=100 |
| 8 |
Correct |
16 ms |
20736 KB |
n=100 |
| 9 |
Correct |
16 ms |
20736 KB |
n=100 |
| 10 |
Correct |
16 ms |
20736 KB |
n=100 |
| 11 |
Correct |
16 ms |
20736 KB |
n=100 |
| 12 |
Incorrect |
16 ms |
20608 KB |
Jury has the answer but participant has not |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
n=5 |
| 2 |
Correct |
16 ms |
20736 KB |
n=100 |
| 3 |
Correct |
50 ms |
20600 KB |
n=100 |
| 4 |
Correct |
47 ms |
20728 KB |
n=100 |
| 5 |
Correct |
16 ms |
20736 KB |
n=100 |
| 6 |
Correct |
16 ms |
20736 KB |
n=100 |
| 7 |
Correct |
16 ms |
20608 KB |
n=100 |
| 8 |
Correct |
16 ms |
20736 KB |
n=100 |
| 9 |
Correct |
16 ms |
20736 KB |
n=100 |
| 10 |
Correct |
16 ms |
20736 KB |
n=100 |
| 11 |
Correct |
16 ms |
20736 KB |
n=100 |
| 12 |
Incorrect |
16 ms |
20608 KB |
Jury has the answer but participant has not |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
n=5 |
| 2 |
Correct |
16 ms |
20736 KB |
n=100 |
| 3 |
Correct |
50 ms |
20600 KB |
n=100 |
| 4 |
Correct |
47 ms |
20728 KB |
n=100 |
| 5 |
Correct |
16 ms |
20736 KB |
n=100 |
| 6 |
Correct |
16 ms |
20736 KB |
n=100 |
| 7 |
Correct |
16 ms |
20608 KB |
n=100 |
| 8 |
Correct |
16 ms |
20736 KB |
n=100 |
| 9 |
Correct |
16 ms |
20736 KB |
n=100 |
| 10 |
Correct |
16 ms |
20736 KB |
n=100 |
| 11 |
Correct |
16 ms |
20736 KB |
n=100 |
| 12 |
Incorrect |
16 ms |
20608 KB |
Jury has the answer but participant has not |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
20736 KB |
n=5 |
| 2 |
Correct |
16 ms |
20736 KB |
n=100 |
| 3 |
Correct |
50 ms |
20600 KB |
n=100 |
| 4 |
Correct |
47 ms |
20728 KB |
n=100 |
| 5 |
Correct |
16 ms |
20736 KB |
n=100 |
| 6 |
Correct |
16 ms |
20736 KB |
n=100 |
| 7 |
Correct |
16 ms |
20608 KB |
n=100 |
| 8 |
Correct |
16 ms |
20736 KB |
n=100 |
| 9 |
Correct |
16 ms |
20736 KB |
n=100 |
| 10 |
Correct |
16 ms |
20736 KB |
n=100 |
| 11 |
Correct |
16 ms |
20736 KB |
n=100 |
| 12 |
Incorrect |
16 ms |
20608 KB |
Jury has the answer but participant has not |
| 13 |
Halted |
0 ms |
0 KB |
- |
