Submission #175528

#TimeUsernameProblemLanguageResultExecution timeMemory
175528VEGAnnBirthday gift (IZhO18_treearray)C++14
0 / 100
24 ms23868 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define PB push_back using namespace std; const int N = 200100; const int PW = 20; set<int> st[N], pr[N]; set<int>::iterator it; vector<int> g[N]; int tin[N], tout[N], up[N][PW], n, m, q, tt = 0, a[N]; void dfs(int v, int p){ up[v][0] = p; for (int po = 1; po < PW; po++) up[v][po] = up[up[v][po - 1]][po - 1]; tin[v] = tt++; for (int u : g[v]){ if (u == p) continue; dfs(u, v); } tout[v] = tt++; } bool upper(int a, int b){ return (tin[a] <= tin[b] && tout[a] >= tout[b]); } int lca(int a, int b){ if (upper(a, b)) return a; if (upper(b, a)) return b; for (int po = PW - 1; po >= 0; po--) if (!upper(up[a][po], b)) a = up[a][po]; return up[a][0]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; for (int i = 1; i < n; i++){ int x, y; cin >> x >> y; x--; y--; g[x].PB(y); g[y].PB(x); } dfs(0, 0); for (int i = 0; i < m; i++){ cin >> a[i]; a[i]--; st[a[i]].insert(i); if (i > 0) pr[lca(a[i], a[i - 1])].insert(i); } for (; q; q--){ int tp; cin >> tp; if (tp == 1){ int ps, v; cin >> ps >> v; ps--; v--; st[a[ps]].erase(ps); if (ps > 0) pr[lca(a[ps], a[ps - 1])].erase(ps); if (ps + 1 < m) pr[lca(a[ps], a[ps + 1])].erase(ps + 1); a[ps] = v; st[a[ps]].insert(ps); if (ps > 0) pr[lca(a[ps], a[ps - 1])].insert(ps); if (ps + 1 < m) pr[lca(a[ps], a[ps + 1])].insert(ps + 1); } else { int l, r, v; cin >> l >> r >> v; l--; r--; v--; int x = -2, y = -2; if (sz(st[v])){ it = st[v].lower_bound(l); if (it != st[v].end() && (*it) <= r){ y = x = (*it); } } if (x < 0 && sz(pr[v])){ it = pr[v].lower_bound(l); if (it != pr[v].end() && (*it) <= r){ y = (*it); x = y - 1; } } cout << x + 1 << " " << y + 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...