Submission #1079501

#TimeUsernameProblemLanguageResultExecution timeMemory
1079501Khanhcsp2Birthday gift (IZhO18_treearray)C++14
56 / 100
2323 ms83152 KiB
#include<bits/stdc++.h> #define el '\n' #define fi first #define sc second #define int ll #define pii pair<int, int> #define all(v) v.begin(), v.end() using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; const int mod=1e9+7; const int N=1e5+11; int n, m, q, up[23][N], h[N], nod[4*N], lc[2003][2003], a[N]; vector<int> adj[N]; void dfs(int u, int pa) { up[0][u]=pa; for(int i=1; i<=20; i++) up[i][u]=up[i-1][up[i-1][u]]; for(int v:adj[u]) { if(v!=pa) { h[v]=h[u]+1; dfs(v, u); } } } int jump(int k, int u) { for(int i=0; i<=20; i++) { if(k>>i&1) u=up[i][u]; } return u; } int lca(int u, int v) { if(h[u]<h[v]) swap(u, v); u=jump(h[u]-h[v], u); if(u==v) return u; for(int i=20; i>=0; i--) { if(up[i][u]!=up[i][v]) { u=up[i][u]; v=up[i][v]; } } return up[0][u]; } void glow(int id, int l, int r) { if(l==r) { nod[id]=a[l]; return; } int mid=(l+r)/2; glow(id*2, l, mid); glow(id*2+1, mid+1, r); nod[id]=lc[nod[id*2]][nod[id*2+1]]; } void update(int id, int l, int r, int pos, int val) { if(r<pos||pos<l) return; if(l==r && l==pos) { nod[id]=val; return; } int mid=(l+r)/2; if(pos<=mid) update(id*2, l, mid, pos, val); else update(id*2+1, mid+1, r, pos, val); nod[id]=lc[nod[id*2]][nod[id*2+1]]; } int get(int id, int l, int r, int u, int v) { if(r<u || v<l) return n+1; if(u<=l && r<=v) return nod[id]; int mid=(l+r)/2; int s1=get(id*2, l, mid, u, v); int s2=get(id*2+1, mid+1, r, u, v); return lc[s1][s2]; } void sub1() { while(q--) { int tt; cin >> tt; if(tt==1) { int pos, v; cin >> pos >> v; update(1, 1, m, pos, v); a[pos]=v; } else { int l, r, v; cin >> l >> r >> v; int ch=0, s1, s2; for(int i=l; i<=r; i++) { if(h[a[i]]<h[v] || ch) continue; int low=i, high=r; while(low<=high) { int mid=(low+high)/2; int cc=get(1, 1, m, i, mid); if(h[cc]>h[v]) low=mid+1; else if(h[cc]<h[v]) high=mid-1; else if(cc==v) { ch=1; s1=i; s2=mid; break; } else break; } } if(ch) cout << s1 << ' ' << s2 << el; else cout << -1 << ' ' << -1 << el; } } } void sol() { cin >> n >> m >> q; for(int i=1; i<n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } h[1]=1; dfs(1, 0); for(int i=1; i<=m; i++) cin >> a[i]; for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) lc[i][j]=lc[j][i]=lca(i, j); for(int i=1; i<=n; i++) lc[n+1][i]=lc[i][n+1]=i; glow(1, 1, m); // cout << get(1, 1, m, 1, 1) << el; sub1(); // cout << lca(5, 3); } signed main() { // freopen("divisor.INP", "r", stdin); // freopen("divisor.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { sol(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...