Submission #847042

#TimeUsernameProblemLanguageResultExecution timeMemory
847042GrandTiger1729Birthday gift (IZhO18_treearray)C++17
100 / 100
1076 ms78944 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, q; cin >> n >> m >> q; vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } vector<int> in(n), out(n); vector<vector<int>> up(n, vector<int>(__lg(n) + 1)); { int t = 0; vector<bool> vis(n); function<void(int)> dfs = [&](int u) { vis[u] = 1; in[u] = t++; for (int i = 1; i <= __lg(n); i++) up[u][i] = up[up[u][i - 1]][i - 1]; for (auto &v : g[u]) { if (vis[v]) continue; up[v][0] = u; dfs(v); } out[u] = t; }; dfs(0); } auto anc = [&](int u, int v) -> bool { return in[u] <= in[v] && out[u] >= out[v]; }; auto lca = [&](int u, int v) -> int { if (anc(u, v)) return u; for (int i = __lg(n); i >= 0; i--) if (!anc(up[u][i], v)) u = up[u][i]; return up[u][0]; }; vector<int> a(m); for (int i = 0; i < m; i++) cin >> a[i], a[i]--; vector<set<pair<int, int>>> mp(n); for (int i = 0; i < m; i++) mp[a[i]].emplace(i, i); for (int i = 0; i < m - 1; i++) mp[lca(a[i], a[i + 1])].emplace(i, i + 1); while (q--) { int ty; cin >> ty; if (ty == 1) { int i, u; cin >> i >> u; i--, u--; if (i > 0) mp[lca(a[i - 1], a[i])].erase(make_pair(i - 1, i)); if (i < m - 1) mp[lca(a[i], a[i + 1])].erase(make_pair(i, i + 1)); mp[a[i]].erase(make_pair(i, i)); a[i] = u; if (i > 0) mp[lca(a[i - 1], a[i])].emplace(i - 1, i); if (i < m - 1) mp[lca(a[i], a[i + 1])].emplace(i, i + 1); mp[a[i]].emplace(i, i); } else { int l, r, u; cin >> l >> r >> u; l--, u--; auto it = mp[u].lower_bound(make_pair(l, -1)); if (it != mp[u].end() && it->first < r && it->second < r) cout << it->first + 1 << ' ' << it->second + 1 << '\n'; else cout << "-1 -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...