Submission #1134823

#TimeUsernameProblemLanguageResultExecution timeMemory
1134823Halym2007Birthday gift (IZhO18_treearray)C++17
0 / 100
23 ms47428 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sz size() #define ff first #define ss second #define pb push_back #define pii pair <int, int> #define dur exit(0) #define dur1 return(0) const int N = 2e6 + 5; const int LOG = 21; int uzyn[N], dp[N][LOG], height[N], a[N]; vector <int> v[N]; void dfs (int x, int par, int height) { uzyn[x] = height; dp[x][0] = par; for (int i : v[x]) { if (i == par) continue; dfs (i, x, height + 1); } } int kth_ancestor (int x, int k) { for (int i = LOG - 1; i >= 0; i--) { if (k>>i&1) { x = dp[x][i]; } } return x; } int lca (int x, int y) { if (height[x] < uzyn[y]) { y = kth_ancestor (y, uzyn[y] - uzyn[x]); } if (height[x] > height[y]) { x = kth_ancestor (x, uzyn[x] - uzyn[y]); } for (int i = LOG - 1; i >= 0; i--) { if (dp[x][i] != dp[y][i]) { x = dp[x][i]; y = dp[y][i]; } } return dp[x][0]; } int main () { // freopen ("input.txt", "r", stdin); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 1; i < n; ++i) { int l, r; cin >> l >> r; v[l].pb (r); v[r].pb (l); } set <int> s[n + 1], s1[n + 1]; dfs (1, -1, 0); for (int i = 1; i < LOG; ++i) { for (int j = 1; j <= n; ++j) { dp[j][i] = dp[dp[j][i - 1]][i - 1]; } } for (int i = 1; i <= m; ++i) { cin >> a[i]; s[a[i]].insert (i); if (i > 1) { s1[lca (a[i], a[i - 1])].insert (i - 1); // cout << a[i] << " " << a[i - 1] << "--> " << lca (a[i], a[i - 1]) << "\n"; } } while ( q-- ) { int tp; cin >> tp; if (tp == 1) { int pos, val; cin >> pos >> val; // update s[a[pos]].erase (pos); s[val].insert (pos); if (pos > 1) { s1[lca (a[pos], a[pos - 1])].erase (pos - 1); s1[lca (a[pos - 1], val)].insert (pos - 1); } if (pos < n) { s1[lca (a[pos], a[pos + 1])].erase (pos); s1[lca (val, a[pos + 1])].insert (pos); } a[pos] = val; } else { int l, r, val; cin >> l >> r >> val; auto tr = s[val].lower_bound (l); if (tr != s[val].end()) { int x = *tr; if (x <= r) { cout << x << " " << x << "\n"; continue; } } tr = s1[val].lower_bound (l); if (tr != s1[val].end()) { int x = *tr; if (x < r) { cout << x << " " << x + 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...