Submission #894024

#TimeUsernameProblemLanguageResultExecution timeMemory
894024PekibanBirthday gift (IZhO18_treearray)C++17
0 / 100
11 ms58972 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 2e5+2, LOG = 20; vector<int> g[mxN]; multiset<int> st[4*mxN]; int up[LOG][mxN], dep[mxN], _m; void build(const vector<int> &v, int i = 1, int l2 = 0, int r2 = _m - 1) { if (l2 == r2) { st[i].insert(v[l2]); return; } int m2 = (l2 + r2)/2; build(v, 2*i, l2, m2); build(v, 2*i+1, m2+1, r2); for (auto u : st[2*i]) { st[i].insert(u); } for (auto u : st[2*i+1]) { st[i].insert(u); } } void update(int l, int x, int y, int i = 1, int l2 = 0, int r2 = _m - 1) { st[i].erase(st[i].find(y)); st[i].insert(x); if (l2 == r2) return; int m2 = (l2 + r2)/2; if (l <= m2) { update(l, x, y, 2*i, l2, m2); } else { update(l, x, y, 2*i+1, m2+1, r2); } } bool wtf = 1; int query(int l, int r, int u, int i = 1, int l2 = 0, int r2 = _m - 1) { if (l <= l2 && r2 <= r) { if (st[i].find(u) != st[i].end()) { while (l2 != r2) { int m2 = (l2 + r2)/2; if (st[2*i].find(u) != st[2*i].end()) { r2 = m2; i = 2*i; } else { l2 = m2+1; i = 2*i+1; } } wtf = 0; return l2; } return -1; } int m2 = (l2 + r2)/2; if (l <= m2) { int x = query(l, r, u, 2*i, l2, m2); if (x != -1) return x; } if (m2 + 1 <= r) { int x = query(l, r, u, 2*i+1, m2+1, r2); if (x != -1) return x; } return -1; } void dfs(int s, int e) { for (auto u : g[s]) { if (u == e) continue; up[0][u] = s, dep[u] = dep[s] + 1; dfs(u, s); } } int jump(int s, int k) { for (int i = 0; i < LOG; ++i) { if ((1 << i) & k) { s = up[i][s]; } } return s; } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); u = jump(u, dep[u] - dep[v]); for (int i = LOG-1; i >= 0; --i) { if (up[i][u] != up[i][v]) { u = up[i][u], v = up[i][v]; } } return up[0][u]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; _m = m-1; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v), g[v].push_back(u); } dfs(0, -1); for (int i = 1; i < LOG; ++i) { for (int j = 0; j < n; ++j) { up[i][j] = up[i-1][up[i-1][j]]; } } int a[m]; multiset<int> ms[n]; vector<int> val(m-1); for (int i = 0; i < n; ++i) ms[i].insert(1e9); for (int i = 0; i < m; ++i) { cin >> a[i]; a[i]--; if (i) { val[i-1] = lca(a[i-1], a[i]); } ms[a[i]].insert(i); } build(val); while (q--) { int t; cin >> t; if (t == 1) { int l, u; cin >> l >> u; l--, u--; if (l != m-1) { int x = lca(u, a[l+1]); update(l, lca(u, a[l+1]), val[l]); val[l] = x; } if (l) { int x = lca(u, a[l-1]); update(l-1, x, val[l-1]); val[l-1] = x; } ms[a[l]].erase(ms[a[l]].find(l)); ms[u].insert(l); a[l] = u; } if (t == 2) { int l, r, v; cin >> l >> r >> v; l--, r--, v--; if (l == r) { if (a[l] == v) { cout << l+1 << ' ' << l+1 << '\n'; } else { cout << -1 << ' ' << -1 << '\n'; } continue; } if (*ms[v].lower_bound(l) <= r) { cout << *ms[v].lower_bound(l)+1 << ' ' << *ms[v].lower_bound(l)+1 << '\n'; } else { int x = query(l, r-1, v); if (x != -1) { cout << x+1 << ' ' << x+2 << '\n'; } else { cout << -1 << ' ' << -1 << '\n'; } } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...