Submission #492350

#TimeUsernameProblemLanguageResultExecution timeMemory
492350RainbowbunnyBirthday gift (IZhO18_treearray)C++17
100 / 100
958 ms84680 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; const int MAXL = 20; int n, m, q; int up[MAXN][MAXL], a[MAXN], H[MAXN]; vector <int> Adj[MAXN]; set <int> Pos[MAXN]; set <int> Nex[MAXN]; void DFS(int node, int p = 1) { up[node][0] = p; for(int i = 1; i < MAXL; i++) { up[node][i] = up[up[node][i - 1]][i - 1]; } for(auto x : Adj[node]) { if(x == p) { continue; } H[x] = H[node] + 1; DFS(x, node); } } int LCA(int u, int v) { if(H[u] < H[v]) { swap(u, v); } int tmp = H[u] - H[v]; for(int i = MAXL - 1; i >= 0; i--) { if(tmp & (1 << i)) { u = up[u][i]; } } if(u == v) { return u; } for(int i = MAXL - 1; i >= 0; i--) { if(up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; Adj[u].push_back(v); Adj[v].push_back(u); } DFS(1); for(int i = 1; i <= m; i++) { cin >> a[i]; Pos[a[i]].insert(i); if(i != 1) { Nex[LCA(a[i - 1], a[i])].insert(i - 1); } } while(q--) { int Type; cin >> Type; if(Type == 1) { int pos, v; cin >> pos >> v; Pos[a[pos]].erase(pos); Pos[v].insert(pos); if(pos > 1) { Nex[LCA(a[pos - 1], a[pos])].erase(pos - 1); Nex[LCA(a[pos - 1], v)].insert(pos - 1); } if(pos < m) { Nex[LCA(a[pos], a[pos + 1])].erase(pos); Nex[LCA(a[pos + 1], v)].insert(pos); } a[pos] = v; } else { int l, r, v; cin >> l >> r >> v; set <int> :: iterator it; it = Pos[v].lower_bound(l); if(it != Pos[v].end() and *it <= r) { cout << *it << ' ' << *it << '\n'; continue; } it = Nex[v].lower_bound(l); if(it != Nex[v].end() and *it < r) { cout << *it << ' ' << *it + 1 << '\n'; continue; } 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...