Submission #167664

#TimeUsernameProblemLanguageResultExecution timeMemory
167664shuvi_dolaBirthday gift (IZhO18_treearray)C++14
100 / 100
1513 ms81964 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; vector <int> g[N]; int a[N], dep[N], par[N][23]; set <int> posver[N], poslca[N]; int n, m, q; void dfs(int s, int p) { par[s][0] = p; for(int i = 1; i <= 20; i++) { par[s][i] = par[par[s][i - 1]][i - 1]; } for(auto u : g[s]) { if(u == p) continue; dep[u] = dep[s] + 1; dfs(u, s); } } int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); for(int i = 20; i >= 0; i--) if(dep[u] - dep[v] >= (1 << i)) u = par[u][i]; if(u == v) return u; for(int i = 20; i >= 0; i--) if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i]; return par[u][0]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); for(int i = 1; i <= m; i++) { cin >> a[i]; posver[a[i]].insert(i); if(i > 1) poslca[lca(a[i], a[i - 1])].insert(i); } while(q--) { int typ, x, y ,ver; cin >> typ >> x >> y; if(typ == 1) { posver[a[x]].erase(x); if(x > 1) poslca[lca(a[x], a[x - 1])].erase(x); if(x < m) poslca[lca(a[x], a[x + 1])].erase(x + 1); a[x] = y; posver[a[x]].insert(x); if(x > 1) poslca[lca(a[x], a[x - 1])].insert(x); if(x < m) poslca[lca(a[x], a[x + 1])].insert(x + 1); } else { cin >> ver; if(posver[ver].size() > 0) { auto L = posver[ver].lower_bound(x); if(L != posver[ver].end() && *L <= y) { cout << *L << ' ' << *L << '\n'; continue; } } if(poslca[ver].size() > 0) { auto L = poslca[ver].lower_bound(x + 1); if(L != poslca[ver].end() && *L <= y) { cout << (*L) - 1 << ' ' << *L << '\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...