Submission #500225

#TimeUsernameProblemLanguageResultExecution timeMemory
500225nickmet2004Birthday gift (IZhO18_treearray)C++11
100 / 100
1244 ms87128 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n , m , q , a[N]; vector<int> adj[N]; int P[N][20],depth[N]; set<int> A[N] , B[N]; void dfs(int u , int p = 0){ P[u][0] = p; for(int i = 1; i <= 18; ++i)P[u][i] = P[P[u][i - 1]][i - 1]; for(int v : adj[u]){ if(v==p)continue; depth[v]=depth[u]+1; dfs(v , u); } } int LCA(int u , int v){ if(depth[u] < depth[v])swap(u , v); int k = depth[u] - depth[v]; for(int i = 18; ~i; --i){ if(k>>i&1) u = P[u][i]; } if(u==v)return u; for(int i= 18; ~i; --i){ if(P[u][i] != P[v][i]) u = P[u][i] , v= P[v][i]; } return P[u][0]; } void upd(int pos , int v){ int y; if(pos >1){ y = LCA(a[pos - 1] ,a[pos]); A[y].erase(pos - 1); A[LCA(a[pos - 1] , v)].insert(pos - 1); } if(pos < m){ y = LCA(a[pos] , a[pos + 1]); A[y].erase(pos); A[LCA(a[pos+1] , v)].insert(pos); } B[a[pos]].erase(pos); B[v].insert(pos); a[pos]=v; return; } void get(int l , int r , int v){ auto it = B[v].lower_bound(l); if(it != B[v].end() && *it <= r){ cout << *it << " " << *it << endl; return; } it = A[v].lower_bound(l); if(it != A[v].end() && *it + 1 <= r){ cout << *it << " " << *it + 1<<endl; return; } cout<<-1 << " " << -1<<endl; } int main (){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m>>q; int u ,v; for(int i= 1; i< n; ++i){ cin >> u >> v; adj[u].emplace_back(v);adj[v].emplace_back(u); } for(int i= 1; i<= m; ++i)cin >> a[i]; dfs(1); for(int i= 1; i <= m; ++i){ int X = LCA(a[i] , a[i + 1]); if(i<m)A[X].insert(i); B[a[i]].insert(i); } while(q--){ int x; cin >> x; if(x==1){ int pos , v; cin >> pos >> v; upd(pos , v); }else{ int l , r ,v; cin >> l >> r >> v; get( l , r , v); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...