Submission #570613

#TimeUsernameProblemLanguageResultExecution timeMemory
570613SSRSBirthday gift (IZhO18_treearray)C++14
100 / 100
1721 ms94788 KiB
#include <bits/stdc++.h> using namespace std; const int LOG = 18; struct lowest_common_ancestor{ vector<int> d; vector<vector<int>> pp; lowest_common_ancestor(vector<int> &p, vector<int> &d): d(d){ int N = p.size(); pp = vector<vector<int>>(LOG, vector<int>(N, -1)); pp[0] = p; for (int i = 0; i < LOG - 1; i++){ for (int j = 0; j < N; j++){ if (pp[i][j] != -1){ pp[i + 1][j] = pp[i][pp[i][j]]; } } } } int lca(int u, int v){ if (d[u] > d[v]){ swap(u, v); } for (int i = 0; i < LOG; i++){ if (((d[v] - d[u]) >> i & 1) == 1){ v = pp[i][v]; } } if (u == v){ return u; } else { for (int i = LOG - 1; i >= 0; i--){ if (pp[i][u] != pp[i][v]){ u = pp[i][u]; v = pp[i][v]; } } return pp[0][u]; } } }; int main(){ int n, m, q; cin >> n >> m >> q; vector<vector<int>> E(n); for (int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } vector<int> a(m); for (int i = 0; i < m; i++){ cin >> a[i]; a[i]--; } vector<int> p(n, -1); vector<int> d(n, 0); queue<int> Q; Q.push(0); while (!Q.empty()){ int v = Q.front(); Q.pop(); for (int w : E[v]){ if (w != p[v]){ p[w] = v; d[w] = d[v] + 1; Q.push(w); } } } lowest_common_ancestor T(p, d); vector<set<int>> st1(n); for (int i = 0; i < m; i++){ st1[a[i]].insert(i); } for (int i = 0; i < n; i++){ st1[i].insert(m); } vector<set<int>> st2(n); for (int i = 0; i < m - 1; i++){ st2[T.lca(a[i], a[i + 1])].insert(i); } for (int i = 0; i < n; i++){ st2[i].insert(m - 1); } for (int i = 0; i < q; i++){ int t; cin >> t; if (t == 1){ int pos, v; cin >> pos >> v; pos--; v--; st1[a[pos]].erase(pos); if (pos > 0){ st2[T.lca(a[pos - 1], a[pos])].erase(pos - 1); } if (pos < m - 1){ st2[T.lca(a[pos], a[pos + 1])].erase(pos); } a[pos] = v; st1[a[pos]].insert(pos); if (pos > 0){ st2[T.lca(a[pos - 1], a[pos])].insert(pos - 1); } if (pos < m - 1){ st2[T.lca(a[pos], a[pos + 1])].insert(pos); } } if (t == 2){ int l, r, v; cin >> l >> r >> v; l--; v--; auto itr1 = st1[v].lower_bound(l); if (*itr1 < r){ cout << *itr1 + 1 << ' ' << *itr1 + 1 << endl; } else { auto itr2 = st2[v].lower_bound(l); if (*itr2 < r - 1){ cout << *itr2 + 1 << ' ' << *itr2 + 2 << endl; } else { cout << -1 << ' ' << -1 << endl; } } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...