Submission #651193

#TimeUsernameProblemLanguageResultExecution timeMemory
651193pccBirthday gift (IZhO18_treearray)C++14
12 / 100
4 ms348 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 = 1e3+10; vector<int> paths[mxn]; int fa[mxn],link_top[mxn],bs[mxn],sz[mxn],dep[mxn],arr[mxn]; 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; } 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]; } // cout<<lca(3,4); while(q--){ int t; cin>>t; if(t == 1){ int p,v; cin>>p>>v; arr[p] = v; } else{ int l,r,v; cin>>l>>r>>v; pii ans = {-1,-1}; for(int i = l;i<=r;i++){ int now = arr[i]; for(int j= i;j<=r;j++){ now = lca(now,arr[j]); if(now == v){ ans = {i,j}; } } } 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...