# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672434 | Cutebol | Birthday gift (IZhO18_treearray) | C++17 | 5 ms | 9812 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
const int N = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e12 ;
int n , m , q , l = 1 , timer ;
int prv[N] , tin[N] , tout[N] , a[N] ;
vector <int> g[N] , up[N] ;
void dfs( int v , int p = 1 ){
tin[v] = ++timer ;
up[v][0] = p ;
for ( int i = 1 ; i <= l ; i ++ ) up[v][i] = up[up[v][i-1]][i-1] ;
for ( auto to : g[v] ){
if ( to != p ) dfs(to ,v) ;
}
tout[v] = ++ timer ;
}
bool upper( int a , int b ){
return tin[a] <= tin[b] && tout[a] >= tout[b] ;
}
int lca ( int a , int b ){
if ( upper(a,b) ) return a ;
if ( upper(b,a) ) return b ;
for ( int i = l ; i >= 0 ; i -- )
if ( !upper(up[a][i] , b) ) a = up[a][i] ;
return up[a][0] ;
}
void solve(){
cin >> n >> m >> q ;
while ( ( 1 << l ) <= n ) l ++ ;
for ( int i = 0 ; i <= n ; i ++ ) up[i].resize(n) ;
for ( int i = 0 ; i < n - 1 ; i ++ ){
int x , y ;
cin >> x >> y ;
g[x].push_back(y) ;
g[y].push_back(x) ;
}
for ( int i = 0 ; i < m ; i ++ ) cin >> a[i] ;
dfs(1) ;
for ( int i = 0 ; i < n ; i ++ ){
if ( i ) prv[i] = lca(a[i] , a[i-1]) ;
else prv[i] = -1 ;
}
while ( q -- ){
int tt ;
cin >> tt ;
if ( tt == 1 ){
int ind , val ;
cin >> ind >> val ;
ind -- ;
a[ind] = val ;
if (ind) prv[ind] = lca ( a[ind] , a[ind-1] ) ;
}
else{
bool f = 0 ;
int l , r , v ;
cin >> l >> r >> v ;
l -- , r -- ;
for ( int i = l ; i <= r; i ++ ){
if ( a[i] == v ){
cout << i+1 << ' ' << i+1 << endl ;
f = 1 ;
break ;
}
}
if ( f ) continue ;
for ( int i = l+1 ; i <= r ; i ++ ){
if ( prv[i] == v ){
cout << i << ' ' << i+1 << endl ;
f = 1 ;
break ;
}
}
if ( f ) continue ;
cout << -1 << ' ' << -1 << endl ;
}
}
}
signed main(){
// fopn("blocks") ;
Scaramouche ;
int t = 1 ;
// cin >> t ;
while ( t -- ) solve() ;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |