Submission #441629

#TimeUsernameProblemLanguageResultExecution timeMemory
441629vishesh312Birthday gift (IZhO18_treearray)C++17
100 / 100
1174 ms77656 KiB
#include "bits/stdc++.h" using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; */ #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)(x).size() using ll = long long; const int mod = 1e9+7; vector<vector<int>> adj; vector<int> depth; vector<array<int, 20>> up; void dfs(int u, int p = -1) { for (int v : adj[u]) { if (v != p) { depth[v] = depth[u] + 1; up[v][0] = u; for (int l = 1; l < 20; ++l) { up[v][l] = up[up[v][l-1]][l-1]; } dfs(v, u); } } } void solve(int tc) { int n, m, q; cin >> n >> m >> q; adj.resize(n); up.resize(n); depth.resize(n); for (int i = 0; i < n-1; ++i) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); adj[v].push_back(u); } dfs(0); auto get_lca = [&] (int u, int v) { if (depth[u] < depth[v]) swap(u, v); int k = depth[u] - depth[v]; for (int l = 19; l >= 0; --l) if (k & (1<<l)) u = up[u][l]; if (u == v) return u; for (int l = 19; l >= 0; --l) { if (up[u][l] != up[v][l]) { u = up[u][l]; v = up[v][l]; } } return up[u][0]; }; vector<set<int>> lca(n); vector<set<int>> pos(n); vector<int> a(m); for (auto &x : a) { cin >> x; --x; } for (int i = 0; i < m; ++i) pos[a[i]].insert(i); for (int i = 0; i < m-1; ++i) { int u = get_lca(a[i], a[i+1]); lca[u].insert(i); } while (q--) { int x; cin >> x; if (x == 1) { int p, v; cin >> p >> v; --p, --v; pos[a[p]].erase(p); pos[v].insert(p); if (p) { lca[get_lca(a[p-1], a[p])].erase(p-1); lca[get_lca(a[p-1], v)].insert(p-1); } if (p < m-1) { lca[get_lca(a[p], a[p+1])].erase(p); lca[get_lca(v, a[p+1])].insert(p); } a[p] = v; } else { int l, r, v; cin >> l >> r >> v; --l, --r, --v; auto it = pos[v].lower_bound(l); int p = *it; if (it != pos[v].end() and p <= r) { cout << p+1 << " " << p+1 << '\n'; continue; } it = lca[v].lower_bound(l); p = *it; if (it != lca[v].end() and p < r) { cout << p+1 << " " << p+2 << '\n'; continue; } cout << "-1 -1\n"; } } } signed main() { cin.tie(0)->sync_with_stdio(0); int tc = 1; //cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); 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...