# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
50911 | Nicksechko | Birthday gift (IZhO18_treearray) | C++14 | 3233 ms | 300008 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
/*
ll pw(ll a, ll b) {
ll ans = 1; while (b) {
while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
ans = (ans * a) % MOD, --b;
} return ans;
}
*/
const int LOG = 20;
const int MAXN = 220000;
int tin[MAXN];
int tout[MAXN];
int up[LOG][MAXN];
vector<int> eds[MAXN];
set<int> g1[MAXN];
set<int> g2[MAXN];
int tm1;
int a[MAXN];
int n, m, q;
void dfs1(int v, int p) {
tin[v] = tm1++;
for (int u: eds[v]) {
if (u == p)
continue;
up[0][u] = v;
dfs1(u, v);
}
tout[v] = tm1;
}
int is_p(int a, int b) {
return tin[a] <= tin[b] && tin[b] < tout[a];
}
int lca(int a, int b) {
if (is_p(a, b))
return a;
for (int i = LOG - 1; i >= 0; --i) {
if (!is_p(up[i][a], b))
a = up[i][a];
}
return up[0][a];
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 0; i < n - 1; ++i) {
int a, b;
scanf("%d%d", &a, &b);
--a, --b;
eds[a].push_back(b);
eds[b].push_back(a);
}
for (int i = 0; i < m; ++i) {
scanf("%d", a + i);
--a[i];
}
dfs1(0, -1);
for (int i = 1; i < LOG; ++i) {
for (int j = 0; j < n; ++j)
up[i][j] = up[i - 1][up[i - 1][j]];
}
for (int i = 0; i < m; ++i) {
g1[a[i]].insert(i);
if (i < m - 1)
g2[lca(a[i], a[i + 1])].insert(i);
}
for (int i = 0; i < q; ++i) {
int t;
scanf("%d", &t);
if (t == 1) {
int ps, v;
scanf("%d%d", &ps, &v);
--ps, --v;
g1[a[ps]].erase(ps);
if (ps < m - 1)
g2[lca(a[ps], a[ps + 1])].erase(ps);
if (ps > 0)
g2[lca(a[ps], a[ps - 1])].erase(ps - 1);
a[ps] = v;
g1[a[ps]].insert(ps);
if (ps < m - 1)
g2[lca(a[ps], a[ps + 1])].insert(ps);
if (ps > 0)
g2[lca(a[ps], a[ps - 1])].insert(ps - 1);
}
else {
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
--l, --r, --v;
auto it1 = g1[v].lower_bound(l);
if (it1 != g1[v].end() && *it1 <= r) {
printf("%d %d\n", *it1 + 1, *it1 + 1);
}
else {
auto it2 = g2[v].lower_bound(l);
if (it2 != g2[v].end() && *it2 < r) {
printf("%d %d\n", *it2 + 1, *it2 + 1 + 1);
}
else {
printf("-1 -1\n");
}
}
}
}
return 0;
}
Compilation message (stderr)
# | 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... |