Submission #1240898

#TimeUsernameProblemLanguageResultExecution timeMemory
1240898_callmelucianBirthday gift (IZhO18_treearray)C++17
100 / 100
410 ms69372 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pl = pair<ll,ll>; using pii = pair<int,int>; using tpl = tuple<int,int,int>; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 2e5 + 5; int node[mn], sz[mn], par[mn], chain[mn], depth[mn]; set<int> appear[mn], itself[mn]; vector<int> adj[mn]; int szDfs (int u, int p) { sz[u] = 1; for (int v : adj[u]) if (v != p) sz[u] += szDfs(v, u); return sz[u]; } void dfs (int u, int p, int d, bool toP) { if (u == 1) szDfs(u, p); par[u] = p, chain[u] = (toP ? chain[p] : u), depth[u] = d; sort(all(adj[u]), [&] (int a, int b) { return sz[a] > sz[b]; }); bool heavy = 1; for (int v : adj[u]) if (v != p) dfs(v, u, d + 1, heavy), heavy = 0; } int lca (int a, int b) { while (chain[a] != chain[b]) { int ap = par[chain[a]], bp = par[chain[b]]; if (depth[ap] == depth[bp]) a = ap, b = bp; else if (depth[ap] > depth[bp]) a = ap; else if (depth[bp] > depth[ap]) b = bp; } return (depth[a] < depth[b] ? a : b); } void addNode (int i) { appear[lca(node[i - 1], node[i])].insert(i); } void removeNode (int i) { appear[lca(node[i - 1], node[i])].erase(i); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0, 1, 0); for (int i = 1; i <= m; i++) { cin >> node[i]; itself[node[i]].insert(i); } for (int i = 2; i <= m; i++) addNode(i); while (q--) { int type; cin >> type; if (type == 1) { int pos, v; cin >> pos >> v; removeNode(pos), removeNode(pos + 1), itself[node[pos]].erase(pos); node[pos] = v; addNode(pos), addNode(pos + 1), itself[node[pos]].insert(pos); } else { int l, r, v; cin >> l >> r >> v; auto it = appear[v].upper_bound(l); if (it != appear[v].end() && *it <= r) cout << *it - 1 << " " << *it << "\n"; else { it = itself[v].lower_bound(l); if (it != itself[v].end() && *it <= r) cout << *it << " " << *it << "\n"; else cout << "-1 -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...