이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
-------------- | /
| | /
| | /
| * |/ | | ------ *
| | | | / \
| | |\ | | | |\ |
\ | | | \ | | | | \ |
\ | | | \ | | \ / \ |
V | | \ \__/| ----- \ |
*/
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
/*--------------------------------------------------------------------------------------*/
const int N = 2e5 + 25, LGN = 19;
vector<int> edge[N];
int anc[LGN][N], dep[N];
void dfs(int u, int p) {
for(int v : edge[u])
if(v != p)
dep[v] = dep[u] + 1, anc[0][v] = u, dfs(v, u);
}
int lca(int a, int b) {
if(dep[a] < dep[b])
swap(a, b);
for(int i = 0, x = dep[a] - dep[b]; i < LGN; i++)
if(x >> i & 1)
a = anc[i][a];
if(a == b)
return a;
for(int i = LGN - 1; ~i; i--) {
if(anc[i][a] != anc[i][b]) {
a = anc[i][a];
b = anc[i][b];
}
}
return anc[0][a];
}
set<int> one[N], two[N];
signed main() { EmiliaMyWife
int n, m, q;
cin >> n >> m >> q;
for(int i = 1, a, b; i < n; i++) {
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
}
dfs(1, 1);
for(int i = 1; i < LGN; i++)
for(int j = 1; j <= n; j++)
anc[i][j] = anc[i - 1][anc[i - 1][j]];
vector<int> arr(m + 1);
for(int i = 1; i <= m; i++)
cin >> arr[i], one[arr[i]].insert(i);
for(int i = 2; i <= n; i++)
two[lca(arr[i - 1], arr[i])].insert(i - 1);
while(q--) {
int t;
cin >> t;
if(t == 1) {
int p, v;
cin >> p >> v;
one[arr[p]].erase(p);
if(p > 1)
two[lca(arr[p - 1], arr[p])].erase(p - 1);
if(p + 1 <= m)
two[lca(arr[p], arr[p + 1])].erase(p);
arr[p] = v;
one[arr[p]].insert(p);
if(p > 1)
two[lca(arr[p - 1], arr[p])].insert(p - 1);
if(p + 1 <= m)
two[lca(arr[p], arr[p + 1])].insert(p);
}
else {
int l, r, v;
cin >> l >> r >> v;
auto it = one[v].lower_bound(l);
auto it2 = two[v].lower_bound(l);
if(it != one[v].end() && *it <= r)
cout << *it << ' ' << *it << '\n';
else if(it2 != two[v].end() && *it2 < r)
cout << *it2 << ' ' << *it2 + 1 << '\n';
else
cout << "-1 -1\n";
}
}
}
/*
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
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |