제출 #651218

#제출 시각아이디문제언어결과실행 시간메모리
651218pccBirthday gift (IZhO18_treearray)C++14
56 / 100
4065 ms19108 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ld long double #define _all(T) T.begin(),T.end() const int mxn = 2e5+10; vector<int> paths[mxn]; int fa[mxn],link_top[mxn],bs[mxn],sz[mxn],dep[mxn],arr[mxn],adj[mxn]; int segtree[mxn*4+4]; void dfs1(int now,int par){ fa[now] = par; sz[now] = 1; for(auto nxt:paths[now]){ if(nxt == par)continue; dep[nxt] = dep[now]+1; dfs1(nxt,now); if(bs[now] == 0||sz[bs[now]] < sz[nxt])bs[now] = nxt; sz[now] += sz[nxt]; } return; } void dfs2(int now,int top){ link_top[now] = top; if(bs[now])dfs2(bs[now],top); for(auto nxt:paths[now]){ if(nxt == fa[now]||nxt == bs[now])continue; dfs2(nxt,nxt); } return; } int lca(int a,int b){ int ta = link_top[a],tb = link_top[b]; while(ta != tb){ if(dep[ta]<dep[tb]){ swap(ta,tb); swap(a,b); } a = fa[ta]; ta = link_top[a]; } if(dep[a]>dep[b])return b; else return a; } void modify(int now,int l,int r,int p,int v){ if(l == r){ segtree[now] = v; return; } int mid = (l+r)>>1; if(mid>=p)modify(now*2+1,l,mid,p,v); else modify(now*2+2,mid+1,r,p,v); segtree[now] = min(segtree[now*2+1],segtree[now*2+2]); return; } int getval(int now,int l,int r,int s,int e){ if(s<=l&&e>=r)return segtree[now]; int mid = (l+r)>>1; if(mid>=e)return getval(now*2+1,l,mid,s,e); else if(mid<s)return getval(now*2+2,mid+1,r,s,e); else return min(getval(now*2+1,l,mid,s,e),getval(now*2+2,mid+1,r,s,e)); } bool flag = false; int main(){ io int n,m,q; cin>>n>>m>>q; // if(m*m*q*__lg(n)>=1e9)return 0; for(int i = 0;i<n-1;i++){ int a,b; cin>>a>>b; paths[a].push_back(b); paths[b].push_back(a); } dfs1(1,1); dfs2(1,1); for(int i = 1;i<=m;i++){ cin>>arr[i]; } for(int i = 2;i<=m;i++){ adj[i] = lca(arr[i],arr[i-1]); modify(0,0,mxn,i,dep[adj[i]]); } // cout<<dep[lca(arr[1],arr[2])]<<' '<<getval(0,0,mxn,2,2);return 0; while(q--){ int t; cin>>t; if(t == 1){ int p,v; cin>>p>>v; arr[p] = v; if(p != 1)adj[p] = lca(arr[p],arr[p-1]); if(p != m)adj[p+1] = lca(arr[p],arr[p+1]); if(p != 1)modify(0,0,mxn,p,dep[adj[p]]); if(p != m)modify(0,0,mxn,p+1,dep[adj[p+1]]); } else{ int a,b,c; pii ans = {-1,-1}; cin>>a>>b>>c; if(a == 1&&b == 3&&c == 1)flag = true; for(int i = a;i<b;i++){ int l = i+1,r = b; while(l < r){ int mid= (l+r)>>1; // if(flag)cout<<l<<' '<<r<<' '<<getval(0,0,mxn,i+1,mid)<<endl; if(getval(0,0,mxn,i+1,mid)<=dep[c])r = mid; else l = mid+1; } if(getval(0,0,mxn,i+1,r) == dep[c]&&lca(arr[i],c) == c){ ans = {i,r}; } if(arr[i] == c)ans = {i,i}; } if(arr[b] == c)ans = {b,b}; flag = false; cout<<ans.fs<<' '<<ans.sc<<'\n'; } } return 0; } /* 5 4 4 1 2 3 1 3 4 5 3 4 5 2 3 2 1 3 1 1 3 5 2 3 4 5 2 1 3 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...