제출 #988663

#제출 시각아이디문제언어결과실행 시간메모리
988663mannshah1211Birthday gift (IZhO18_treearray)C++17
100 / 100
1200 ms91740 KiB
/** * 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...