이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
const int mxn = 200000, k = __lg(mxn - 1) + 1;
int n, m, q;
int a[mxn], lc[mxn], d[mxn];
int p[k][mxn];
vector<int> g[mxn];
set<pi> s[mxn];
void dfs(int c){
for(int i = 1; i < k; i++) p[i][c] = ~p[i - 1][c] ? p[i - 1][p[i - 1][c]] : -1;
for(int i : g[c]) if(i != p[0][c]) d[i] = d[c] + 1, p[0][i] = c, dfs(i);
}
int lca(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = k - 1; ~i; i--) if(~p[i][x] && d[p[i][x]] >= d[y]) x = p[i][x];
for(int i = k - 1; ~i; i--) if(p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
return x == y ? x : p[0][x];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
p[0][0] = -1;
dfs(0);
for(int i = 0; i < m; i++){
cin >> a[i];
s[--a[i]].insert({i, i});
if(i) s[lc[i - 1] = lca(a[i - 1], a[i])].insert({i - 1, i});
}
while(q--){
int t;
cin >> t;
if(t & 1){
int x, y;
cin >> x >> y;
x--, y--;
s[a[x]].erase({x, x});
if(x) s[lc[x - 1]].erase({x - 1, x});
if(x < m - 1) s[lc[x]].erase({x, x + 1});
s[a[x] = y].insert({x, x});
if(x) s[lc[x - 1] = lca(a[x - 1], a[x])].insert({x - 1, x});
if(x < m - 1) s[lc[x] = lca(a[x], a[x + 1])].insert({x, x + 1});
}else{
int l, r, x;
cin >> l >> r >> x;
l--, r--, x--;
auto it = s[x].lower_bound({l, l});
pi p = it != s[x].end() && it->s <= r ? *it : pi{-2, -2};
cout << p.f + 1 << " " << p.s + 1 << endl;
}
}
return 0;
}
# | 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... |