Submission #667471

#TimeUsernameProblemLanguageResultExecution timeMemory
667471ljubaBirthday gift (IZhO18_treearray)C++17
100 / 100
1335 ms77316 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)(x).size() #define fi first #define se second template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;} template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;} namespace debug { void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);} #ifdef DEBUG #define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x); cerr << "\033[0m"; #else #define dbg(x...) #endif } using namespace debug; const char nl = '\n'; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); void solve() { int n, m, q; cin >> n >> m >> q; vvi adj(n); for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); adj[v].push_back(u); } const int LOG = 31 - __builtin_clz(n) + 2; vvi up(n, vi(LOG)); vi dep(n); auto dfs = [&](auto &self, int s, int p) -> void { up[s][0] = p; for(int i = 1; i < LOG; ++i) { if(up[s][i - 1] == -1) { up[s][i] = -1; } else { up[s][i] = up[up[s][i - 1]][i - 1]; } } for(auto e : adj[s]) { if(e == p) continue; dep[e] = dep[s] + 1; self(self, e, s); } }; dfs(dfs, 0, -1); auto lca = [&](int u, int v) { if(dep[u] < dep[v]) swap(u, v); //dep[u] >= dep[v] int k = dep[u] - dep[v]; for(int i = 0; i < LOG; ++i) { if((k >> i) & 1) { u = up[u][i]; } } if(u == v) return u; for(int i = LOG - 1; i >= 0; --i) { if(up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; } } return up[u][0]; }; vi a(m); for(auto &z : a) cin >> z; for(auto &z : a) --z; set<int> gdeJed[n]; for(int i = 0; i < m; ++i) { gdeJed[a[i]].insert(i); } set<int> gdeDva[n]; for(int i = 0; i + 1 < m; ++i) { int x = lca(a[i], a[i + 1]); gdeDva[x].insert(i); } while(q--) { int t; cin >> t; auto calc = [&](int i) { if(i < 0) return -1; if(i + 1 >= m) return -1; return lca(a[i], a[i + 1]); }; if(t == 1) { int i, v; cin >> i >> v; --i, --v; gdeJed[a[i]].erase(i); int prvi = calc(i - 1); if(prvi != -1) { gdeDva[prvi].erase(i - 1); } int drugi = calc(i); if(drugi != -1) { gdeDva[drugi].erase(i); } a[i] = v; gdeJed[a[i]].insert(i); prvi = calc(i - 1); if(prvi != -1) { gdeDva[prvi].insert(i - 1); } drugi = calc(i); if(drugi != -1) { gdeDva[drugi].insert(i); } } else { int l, r, v; cin >> l >> r >> v; --l, --r, --v; auto it = gdeJed[v].lower_bound(l); if(it != gdeJed[v].end() && *it <= r) { assert((*it >= l) && (*it <= r)); cout << *it + 1 << " " << *it + 1 << nl; continue; } it = gdeDva[v].lower_bound(l); if(it != gdeDva[v].end() && *it + 1 <= r) { assert((*it >= l) && (*it + 1 <= r)); cout << *it + 1 << " " << *it + 2 << nl; continue; } cout << -1 << " " << -1 << nl; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int testCases = 1; //cin >> testCases; while(testCases--) 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...