#include <bits/stdc++.h>
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define pb emplace_back
#define elif else if
#define uns unsigned
#define emp empty()
#define nll nullptr
#define S second
#define F first
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef pair < ll, ll > pll;
typedef pair < int, int > pi;
typedef pair < ldb, ldb > pldb;
typedef vector < pair < ll, ll > > vpll;
typedef vector < pair < int, int > > vpi;
const int N = 2e5 + 11;
const int M = 1e4 + 123;
const int mod = 1e9 + 7;
const int mxlg = 20;
const int K = 21;
const int P = 31;
const ll inf = 1e9 + 10;
//mt19937 rnd(07062006);
int n, m, q;
int a[N], d[N];
int up[N][K];
set < int > s1[N], s2[N];
vector < int > g[N];
void dfs(int v = 1, int p = 0){
up[v][0] = p;
for(int i = 1; i < mxlg; i++) up[v][i] = up[up[v][i - 1]][i - 1];
for(auto to : g[v])
if(to != p)
d[to] = d[v] + 1,
dfs(to, v);
}
int lca(int a, int b) {
int k = d[a] - d[b];
if(d[a] < d[b]) swap(a, b);
for(int i = 0; i < mxlg; i++)
if(((k >> i) & 1))
a = up[a][i];
if(a == b) return a;
for(int i = mxlg - 1; i >= 0; i--)
if(up[a][i] != up[b][i])
a = up[a][i], b = up[b][i];
return up[a][0];
}
void output(){
cin >> n >> m >> q;
for(int u, v, i = 1; i < n; i++){
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
dfs();
for(int i = 1; i <= m; i++) cin >> a[i];
for(int i = 1; i < m; i++){
s1[a[i]].insert(i), s2[lca(a[i], a[i + 1])].insert(i);
// cout << lca(a[i], a[i + 1]) << ' ';
}
while(q--){
int tp;
cin >> tp;
if(tp == 1){
int k, x;
cin >> k >> x;
s1[a[k]].erase(k);
if(k != 1) s2[lca(a[k - 1], a[k])].erase(k - 1);
if(k != n) s2[lca(a[k], a[k + 1])].erase(k);
a[k] = x;
s1[a[k]].insert(k);
if(k != 1) s2[lca(a[k - 1], a[k])].insert(k - 1);
if(k != n) s2[lca(a[k], a[k + 1])].insert(k);
}
else{
int l, r, v;
cin >> l >> r >> v;
auto it1 = s1[v].lower_bound(l);
auto it2 = s2[v].lower_bound(l);
if(it1 != s1[v].end() && *it1 <= r) cout << *it1 << ' ' << *it1 << '\n';
else if(it2 != s2[v].end() && *it2 < r) cout << *it2 << ' ' << *it2 + 1 << '\n';
else cout << "-1 -1\n";
}
}
}
const bool cases = 0;
signed main(){
// file("disrupt");
adiyer();
int tt = 1;
if(cases) cin >> tt;
for(int i = 1; i <= tt; i++){
// cout << "Case " << i << ":\n";
output();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
n=5 |
| 2 |
Correct |
5 ms |
25176 KB |
n=100 |
| 3 |
Correct |
5 ms |
25180 KB |
n=100 |
| 4 |
Incorrect |
6 ms |
25180 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
n=5 |
| 2 |
Correct |
5 ms |
25176 KB |
n=100 |
| 3 |
Correct |
5 ms |
25180 KB |
n=100 |
| 4 |
Incorrect |
6 ms |
25180 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
n=5 |
| 2 |
Correct |
5 ms |
25176 KB |
n=100 |
| 3 |
Correct |
5 ms |
25180 KB |
n=100 |
| 4 |
Incorrect |
6 ms |
25180 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
n=5 |
| 2 |
Correct |
5 ms |
25176 KB |
n=100 |
| 3 |
Correct |
5 ms |
25180 KB |
n=100 |
| 4 |
Incorrect |
6 ms |
25180 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
