제출 #495845

#제출 시각아이디문제언어결과실행 시간메모리
495845NalrimetSegments (IZhO18_segments)C++17
0 / 100
45 ms65540 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; 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]; } int pos, v, l, r, typ; for (int i = 1; i <= q; i++) { cin >> typ; if(typ == 1){ cin >> pos >> v; a[pos] = v; } else{ cin >> l >> r >> v; ans = {-1, -1}; for(int i = l; i <= r; ++i){ if(a[i] == v){ ans = {i, i}; break; } if(i + 1 <= r && lca(a[i], a[i + 1]) == v){ ans = {i, i + 1}; break; } } cout << ans.F << ' ' << ans.S << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...