This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* Speech to the young */
//#include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
/*
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
using namespace std;
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
#define int long long
#define cube (x) ((x) * (x) * (x))
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
void pre(int a) { cout<<fixed<<setprecision(a); }
int bitcount (int x) {return __builtin_popcount (x);}
const int N = 2e5 + 10;
const int INF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int P = 31;
const double eps = 1e-19;
long double pi = 3.1415926535897323;
int n, m, q, depth[N], up[N][22], a[N];
vector <int> g[N];
set <int> sg[N], tw[N];
void dfs (int v, int p) {
up[v][0] = p;
for (int i = 1; i <= 20; ++ i) up[v][i] = up[up[v][i - 1]][i - 1];
for (auto to: g[v]) {
if (to != p) {
depth[to] = depth[v] + 1;
dfs (to, v);
}
}
return;
}
int lca (int a, int b) {
if (depth[a] < depth[b]) swap (a, b);
int k = depth[a] - depth[b];
for (int i = 20; i >= 0; -- i) if (((k >> i) & 1)) a = up[a][i];
if (a == b) return a;
for (int i = 20; i >= 0; -- i) {
if (up[a][i] != up[b][i]) {
a = up[a][i], b = up[b][i];
}
}
return up[a][0];
}
void Solution () {
cin >> n >> m >> q;
int x, y;
for (int i = 1; i < n; ++ i) {
cin >> x >> y;
g[x].pb (y), g[y].pb (x);
}
dfs (1, 0);
for (int i = 1; i <= m; ++ i) {
cin >> a[i];
sg[a[i]].insert (i);
}
for (int i = 1; i < m; ++ i) {
int x = lca (a[i], a[i + 1]);
tw[x].insert (i);
}
while (q --) {
int tp, l, r, v, pos;
cin >> tp;
if (tp == 1) {
cin >> pos >> v;
sg[a[pos]].erase (pos);
if (pos < m) tw[lca (a[pos], a[pos + 1])].erase (pos);
if (pos > 1) tw[lca (a[pos], a[pos - 1])].erase (pos - 1);
a[pos] = v;
sg[v].insert (pos);
if (pos < m) tw[lca (a[pos], a[pos + 1])].insert (pos);
if (pos > 1) tw[lca (a[pos], a[pos - 1])].insert (pos - 1);
} else {
cin >> l >> r >> v;
int x = *sg[v].lower_bound (l);
if (x <= r) {
cout << x << ' ' << x << '\n';
continue;
}
x = *tw[v].lower_bound (l);
// cout << x << ' ';
if (x < r) {
cout << x << ' ' << x + 1 << '\n';
continue;
}
cout << "-1 -1\n";
}
}
}
signed main () {
YOSIK();
// precalc();
int T = 1;
// cin >> T;
for (int i = 1; i < N; ++ i) sg[i].insert (INF), tw[i].insert (INF);
while (T --) Solution ();
exit (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... |