제출 #441546

#제출 시각아이디문제언어결과실행 시간메모리
441546nishuzBirthday gift (IZhO18_treearray)C++17
56 / 100
4043 ms65108 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define ld long double #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pb push_back #define eb emplace_back #define F first #define S second #define mp make_pair #define random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) template <typename T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>; template <typename Container> void Print(Container& container, int starting) { auto Start = container.begin() + starting, End = container.end(); while (Start != End) cout << *(Start++) << " "; cout << '\n'; } template <typename T> void print(T&& t) {cout << t << '\n';} template <typename T, typename... Args> void print(T&& t, Args&&... args) { cout << t << " "; print(forward<Args>(args)...); } const int mxn = 2e5+1, mxk = 19; vector <int> adj[mxn], dep(mxn); vector <vector <int>> par(mxn, vector <int> (mxk, -1)); map <int, set <int>> mm; void dfs(int u, int p, int d) { par[u][0] = p; dep[u] = d; for (int i = 1; i < mxk; ++i) { int t = par[u][i-1]; if (t == -1) continue; par[u][i] = par[t][i-1]; } for (int v : adj[u]) if (v != p) dfs(v, u, d+1); } int kthpar(int n, int k) { for (int i = 0; i < mxk; ++i) if (k & (1 << i)) n = par[n][i]; return n; } int lca(int a, int b) { if (dep[a] > dep[b]) a = kthpar(a, dep[a]-dep[b]); else if (dep[b] > dep[a]) b = kthpar(b, dep[b]-dep[a]); if (a == b) return a; for (int i = mxk-1; i >= 0; --i) { if (par[a][i] != par[b][i]) { a = par[a][i]; b = par[b][i]; } } return par[a][0]; } inline void solve() { int n, m, q; cin >> n >> m >> q; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; adj[u].eb(v); adj[v].eb(u); } vector <int> a(m + 1); for (int i = 1; i <= m; ++i) { cin >> a[i]; mm[a[i]].insert(i); } dfs(1, 0, 0); for (int _ = 0; _ < q; _++) { int t; cin >> t; if (t == 1) { int pos, v; cin >> pos >> v; mm[a[pos]].erase(pos); a[pos] = v; mm[v].insert(pos); } else { int l, r, v; cin >> l >> r >> v; if (l > r) swap(l, r); int hi = *mm[v].lower_bound(l); if (l <= hi && hi <= r) { print(hi, hi); goto END; } for (int i = l; i + 1 <= r; ++i) { if (lca(a[i], a[i + 1]) == v) { print(i, i + 1); goto END; } } print(-1, -1); END:; } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T = 1; // cin >> T; for (int test = 1; test <= T; ++test) { // cout << "Case #" << test << ": "; solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...