Submission #1114062

#TimeUsernameProblemLanguageResultExecution timeMemory
1114062vjudge1Birthday gift (IZhO18_treearray)C++17
56 / 100
4049 ms56772 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> const int MOD = 1e9+7,inf = 2e18; const int N = 2e5+50,Q = 2e5+50; vi edges[N]; int tin[N],tout[N]; int A[N],B[N]; int timer = 1; int up[N][20]; void dfs(int node,int p) { tin[node] = timer++; up[node][0] = p; for (auto it : edges[node]) { if (it != p) dfs(it,node); } tout[node] = timer-1; } bool anc(int a,int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a,int b) { if (anc(a,b)) return a; if (anc(b,a)) return b; for (int i = 19;i>=0;i--) if (!anc(up[a][i],b)) a = up[a][i]; return up[a][0]; } void solve() { int n,m,q; cin >> n >> m >> q; for (int i=1;i<=n-1;i++) { int a,b; cin >> a >> b; edges[a].push_back(b); edges[b].push_back(a); } dfs(1,1); for (int i = 1;i<=m;i++) { cin >> B[i]; } for (int i=1;i<20;i++) { for (int j = 1;j<=n;j++) up[j][i] = up[up[j][i-1]][i-1]; } while (q--) { int type; cin >> type; if (type == 1) { int p,v; cin >> p >> v; A[p] = tin[v], B[p] = v; } else { int l,r,v; cin >> l >> r >> v; int runner = 0; int start = 0; bool fl = 0; for (int j = l;j<=r;j++) { if (!anc(v,B[j])) { runner = 0; continue; } if (!runner) runner = B[j],start = j; else runner = lca(runner,B[j]); if (runner == v) { cout << start << " " << j << '\n'; fl = 1; break; } } if (fl) continue; cout << -1 << " " << -1 << '\n'; } } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) 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...