Submission #495865

#TimeUsernameProblemLanguageResultExecution timeMemory
495865NalrimetBirthday gift (IZhO18_treearray)C++17
100 / 100
1078 ms78012 KiB
//#pragma GCC target("avx2") //#pragma GCC optimization("O3") //#pragma GCC optimization("unroll-loops") //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; const int N = 2 * 1e5 + 5; const int MOD = 1e9 + 7; const int K = 18; int n, m, q, a[N], par[N][K], h[N]; vector<int> g[N]; pair<int, int> ans; set<int> :: iterator it; set<int> ans1[N], ans2[N]; void dfs(int v, int pr){ par[v][0] = pr; for(int to : g[v]){ if(to != pr){ h[to] = h[v] + 1; dfs(to, v); } } } bool bit(int x, int p){ return x & (1 << p); } int lift(int v, int k){ for(int i = 0; i < K; i++){ if (bit(k, i)) { v = par[v][i]; } } return v; } int lca(int a, int b){ if(h[a] < h[b]){ swap(a, b); } a = lift(a, h[a] - h[b]); if(a == b){ return a; } for(int i = K - 1; i >= 0; --i){ if(par[a][i] != par[b][i]){ a = par[a][i]; b = par[b][i]; } } return par[a][0]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for(int i = 1, u, v; i < n; i++){ cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1, 1); for(int i = 1; i < K; i++){ for(int v = 1; v <= n; v++){ par[v][i] = par[par[v][i - 1]][i - 1]; } } for(int i = 1; i <= m; ++i){ cin >> a[i]; ans1[a[i]].insert(i); if(i > 1) ans2[lca(a[i], a[i - 1])].insert(i - 1); } int pos, v, l, r, typ; for (int j = 1; j <= q; j++) { cin >> typ; // cout << q << '\n'; if(typ == 1){ int i; cin >> i >> v; ans1[a[i]].erase(i); if(i > 1) ans2[lca(a[i], a[i - 1])].erase(i - 1); if(i < m){ ans2[lca(a[i], a[i + 1])].erase(i); } a[i] = v; ans1[a[i]].insert(i); if(i > 1) ans2[lca(a[i], a[i - 1])].insert(i - 1); if(i < m){ ans2[lca(a[i], a[i + 1])].insert(i); } } else{ cin >> l >> r >> v; if(ans1[v].empty() && ans2[v].empty()) {cout << "-1 -1\n"; continue;} else{ bool ok = 0; if(ans1[v].size()){ it = ans1[v].lower_bound(l); if(it != ans1[v].end() && *it <= r) ok = 1; } if(ok) {cout << *it << ' ' << *it << '\n'; continue;} if(ans2[v].size()){ it = ans2[v].lower_bound(l); if(it != ans2[v].end() && *it < r) ok = 1; } if(ok) {cout << *it << ' ' << *it + 1 << '\n'; continue;} } cout << "-1 -1\n"; } } return 0; }

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:95:9: warning: unused variable 'pos' [-Wunused-variable]
   95 |     int pos, v, l, r, typ;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...