이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* author: tourist
* created:
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
template <typename T>
class graph {
public:
struct edge {
int from;
int to;
T cost;
};
vector<edge> edges;
vector<vector<int>> g;
int n;
graph(int _n) : n(_n) {
g.resize(n);
}
virtual int add(int from, int to, T cost) = 0;
};
template <typename T>
class forest : public graph<T> {
public:
using graph<T>::edges;
using graph<T>::g;
using graph<T>::n;
forest(int _n) : graph<T>(_n) {
}
int add(int from, int to, T cost = 1) {
assert(0 <= from && from < n && 0 <= to && to < n);
int id = (int) edges.size();
assert(id < n - 1);
g[from].push_back(id);
g[to].push_back(id);
edges.push_back({from, to, cost});
return id;
}
};
template <typename T>
class dfs_forest : public forest<T> {
public:
using forest<T>::edges;
using forest<T>::g;
using forest<T>::n;
vector<int> pv;
vector<int> pe;
vector<int> order;
vector<int> pos;
vector<int> end;
vector<int> sz;
vector<int> root;
vector<int> depth;
vector<T> dist;
dfs_forest(int _n) : forest<T>(_n) {
}
void init() {
pv = vector<int>(n, -1);
pe = vector<int>(n, -1);
order.clear();
pos = vector<int>(n, -1);
end = vector<int>(n, -1);
sz = vector<int>(n, 0);
root = vector<int>(n, -1);
depth = vector<int>(n, -1);
dist = vector<T>(n);
}
void clear() {
pv.clear();
pe.clear();
order.clear();
pos.clear();
end.clear();
sz.clear();
root.clear();
depth.clear();
dist.clear();
}
private:
void do_dfs(int v) {
pos[v] = (int) order.size();
order.push_back(v);
sz[v] = 1;
for (int id : g[v]) {
if (id == pe[v]) {
continue;
}
auto &e = edges[id];
int to = e.from ^ e.to ^ v;
depth[to] = depth[v] + 1;
dist[to] = dist[v] + e.cost;
pv[to] = v;
pe[to] = id;
root[to] = (root[v] != -1 ? root[v] : to);
do_dfs(to);
sz[v] += sz[to];
}
end[v] = (int) order.size() - 1;
}
void do_dfs_from(int v) {
depth[v] = 0;
dist[v] = T{};
root[v] = v;
pv[v] = pe[v] = -1;
do_dfs(v);
}
public:
void dfs(int v, bool clear_order = true) {
if (pv.empty()) {
init();
} else {
if (clear_order) {
order.clear();
}
}
do_dfs_from(v);
}
void dfs_all() {
init();
for (int v = 0; v < n; v++) {
if (depth[v] == -1) {
do_dfs_from(v);
}
}
assert((int) order.size() == n);
}
};
template <typename T>
class lca_forest : public dfs_forest<T> {
public:
using dfs_forest<T>::edges;
using dfs_forest<T>::g;
using dfs_forest<T>::n;
using dfs_forest<T>::pv;
using dfs_forest<T>::pos;
using dfs_forest<T>::end;
using dfs_forest<T>::depth;
int h;
vector<vector<int>> pr;
lca_forest(int _n) : dfs_forest<T>(_n) {
}
inline void build_lca() {
assert(!pv.empty());
int max_depth = 0;
for (int i = 0; i < n; i++) {
max_depth = max(max_depth, depth[i]);
}
h = 1;
while ((1 << h) <= max_depth) {
h++;
}
pr.resize(n);
for (int i = 0; i < n; i++) {
pr[i].resize(h);
pr[i][0] = pv[i];
}
for (int j = 1; j < h; j++) {
for (int i = 0; i < n; i++) {
pr[i][j] = (pr[i][j - 1] == -1 ? -1 : pr[pr[i][j - 1]][j - 1]);
}
}
}
inline bool anc(int x, int y) {
return (pos[x] <= pos[y] && end[y] <= end[x]);
}
inline int go_up(int x, int up) {
assert(!pr.empty());
up = min(up, (1 << h) - 1);
for (int j = h - 1; j >= 0; j--) {
if (up & (1 << j)) {
x = pr[x][j];
if (x == -1) {
break;
}
}
}
return x;
}
inline int lca(int x, int y) {
assert(!pr.empty());
if (anc(x, y)) {
return x;
}
if (anc(y, x)) {
return y;
}
for (int j = h - 1; j >= 0; j--) {
if (pr[x][j] != -1 && !anc(pr[x][j], y)) {
x = pr[x][j];
}
}
return pr[x][0];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
lca_forest<int> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u; --v;
g.add(u, v);
}
g.dfs_all();
g.build_lca();
vector<int> a(m);
for (int i = 0; i < m; i++) {
cin >> a[i];
--a[i];
}
vector<set<pair<int, int>>> at(n);
for (int i = 0; i < m - 1; i++) {
at[g.lca(a[i], a[i + 1])].insert(make_pair(i, i + 1));
}
for (int i = 0; i < m; i++) {
at[a[i]].insert(make_pair(i, i));
}
auto Add = [&](int p) -> void {
at[a[p]].insert(make_pair(p, p));
if (p > 0) {
at[g.lca(a[p - 1], a[p])].insert(make_pair(p - 1, p));
}
if (p < m - 1) {
at[g.lca(a[p], a[p + 1])].insert(make_pair(p, p + 1));
}
};
auto Remove = [&](int p) -> void {
at[a[p]].erase(make_pair(p, p));
if (p > 0) {
at[g.lca(a[p - 1], a[p])].erase(make_pair(p - 1, p));
}
if (p < m - 1) {
at[g.lca(a[p], a[p + 1])].erase(make_pair(p, p + 1));
}
};
while (q--) {
int op;
cin >> op;
if (op == 1) {
int p, v;
cin >> p >> v;
--p; --v;
Remove(p);
a[p] = v;
Add(p);
} else {
int l, r, v;
cin >> l >> r >> v;
--l; --r; --v;
auto it = at[v].lower_bound(make_pair(l, l));
if (it == at[v].end() || it->second > r) {
cout << -1 << " " << -1 << '\n';
} else {
cout << it->first + 1 << " " << it->second + 1 << '\n';
}
}
}
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... |