#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define sc second
#define pb push_back
#define in insert
vector <ll> g[2001], tin(2001) , tout(2001);
ll up[2001][13] , cur;
void dfs (ll v, ll p) {
tin[v] = ++cur;
for (int i = 1; i <= 12; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto k : g[v]) {
if (k == p) continue;
up[k][0] = v;
dfs(k , v);
}
tout[v] = ++cur;
}
bool is_par(ll a, ll b) {
if (tin[a] <= tin[b] && tout[a] >= tout[b]) return 1;
else return 0;
}
ll lca (ll a, ll b) {
if (is_par(a , b)) return a;
if (is_par(b , a)) return b;
for (int i = 12; i >= 0; i--) {
if (!is_par(up[a][i] , b)) a = up[a][i];
}
return up[a][0];
}
void dambo_12() {
ll n , m , q; cin>>n>>m>>q;
for (int i = 1; i < n; i++){
ll a , b; cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
up[1][0] = 1;
dfs(1 , 1);
vector <ll> a(m + 1 , 0);
for (int i = 1; i <= m; i++)
cin>>a[i];
for (int it = 1; it <= q; it++) {
int tp; cin>>tp;
if (tp == 1) {
int pos ; ll v; cin>>pos>>v;
a[pos] = v;
}
else {
int l , r , v; cin>>l>>r>>v;
int x = -1 , y = -1 , check = a[l];
for (int i = l + 1; i <= r; i++) {
check = lca(check , a[i]);
}
if (!is_par(check , v)) {
cout<<-1<<" "<<-1<<'\n'; break;
}
for (int i = l; i <= r; i++){
int c = a[i];
for (int j = i; j <= r; j++){
c = lca(c , a[j]);
if (c == v) {
x = i; y = j; break;
}
if (!is_par(v , c)) break;
}
if (x != -1) break;
}
cout<<x<<" "<<y<<'\n';
}
}
return;
}
int32_t main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll o = 1; //cin>>o;
while (o--) {
dambo_12();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
n=5 |
| 2 |
Correct |
0 ms |
340 KB |
n=100 |
| 3 |
Correct |
1 ms |
340 KB |
n=100 |
| 4 |
Correct |
0 ms |
340 KB |
n=100 |
| 5 |
Correct |
1 ms |
340 KB |
n=100 |
| 6 |
Correct |
1 ms |
340 KB |
n=100 |
| 7 |
Correct |
1 ms |
340 KB |
n=100 |
| 8 |
Correct |
1 ms |
340 KB |
n=100 |
| 9 |
Correct |
1 ms |
340 KB |
n=100 |
| 10 |
Correct |
1 ms |
340 KB |
n=100 |
| 11 |
Correct |
1 ms |
340 KB |
n=100 |
| 12 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
n=5 |
| 2 |
Correct |
0 ms |
340 KB |
n=100 |
| 3 |
Correct |
1 ms |
340 KB |
n=100 |
| 4 |
Correct |
0 ms |
340 KB |
n=100 |
| 5 |
Correct |
1 ms |
340 KB |
n=100 |
| 6 |
Correct |
1 ms |
340 KB |
n=100 |
| 7 |
Correct |
1 ms |
340 KB |
n=100 |
| 8 |
Correct |
1 ms |
340 KB |
n=100 |
| 9 |
Correct |
1 ms |
340 KB |
n=100 |
| 10 |
Correct |
1 ms |
340 KB |
n=100 |
| 11 |
Correct |
1 ms |
340 KB |
n=100 |
| 12 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
n=5 |
| 2 |
Correct |
0 ms |
340 KB |
n=100 |
| 3 |
Correct |
1 ms |
340 KB |
n=100 |
| 4 |
Correct |
0 ms |
340 KB |
n=100 |
| 5 |
Correct |
1 ms |
340 KB |
n=100 |
| 6 |
Correct |
1 ms |
340 KB |
n=100 |
| 7 |
Correct |
1 ms |
340 KB |
n=100 |
| 8 |
Correct |
1 ms |
340 KB |
n=100 |
| 9 |
Correct |
1 ms |
340 KB |
n=100 |
| 10 |
Correct |
1 ms |
340 KB |
n=100 |
| 11 |
Correct |
1 ms |
340 KB |
n=100 |
| 12 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
n=5 |
| 2 |
Correct |
0 ms |
340 KB |
n=100 |
| 3 |
Correct |
1 ms |
340 KB |
n=100 |
| 4 |
Correct |
0 ms |
340 KB |
n=100 |
| 5 |
Correct |
1 ms |
340 KB |
n=100 |
| 6 |
Correct |
1 ms |
340 KB |
n=100 |
| 7 |
Correct |
1 ms |
340 KB |
n=100 |
| 8 |
Correct |
1 ms |
340 KB |
n=100 |
| 9 |
Correct |
1 ms |
340 KB |
n=100 |
| 10 |
Correct |
1 ms |
340 KB |
n=100 |
| 11 |
Correct |
1 ms |
340 KB |
n=100 |
| 12 |
Incorrect |
1 ms |
340 KB |
Unexpected end of file - int32 expected |
| 13 |
Halted |
0 ms |
0 KB |
- |
