# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672478 | Cutebol | Birthday gift (IZhO18_treearray) | C++17 | 1118 ms | 102284 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 tin[N] , tout[N] , a[N] ;
vector <int> g[N] , up[N] ;
set <int> par[N] , st[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(l+1) ;
for ( int i = 1 ; i < n ; i ++ ){
int x , y ;
cin >> x >> y ;
g[x].push_back(y) ;
g[y].push_back(x) ;
}
for ( int i = 1 ; i <= m ; i ++ ){ cin >> a[i] ; st[a[i]].insert(i) ;}
dfs(1) ;
for ( int i = 2 ; i <= m ; i ++ )
par[lca(a[i],a[i-1])].insert(i-1) ;
while ( q -- ){
int tt ;
cin >> tt ;
if ( tt == 1 ){
int ind , val ;
cin >> ind >> val ;
st[a[ind]].erase(ind) ;
st[val].insert(ind) ;
if ( ind > 1 ){
par[lca(a[ind],a[ind-1])].erase(ind-1) ;
par[lca(val,a[ind-1])].insert(ind-1) ;
}
if ( ind < m ){
par[lca(a[ind],a[ind+1])].erase(ind) ;
par[lca(val,a[ind+1])].insert(ind) ;
}
a[ind] = val ;
}
else{
int l , r , v ;
cin >> l >> r >> v ;
auto f = st[v].lower_bound(l) ;
if ( f != st[v].end() && *f <= r ){
cout << *f << ' ' << *f << endl ;
continue ;
}
f = par[v].lower_bound(l) ;
if ( f != par[v].end() && *f < r )
cout << *f << ' ' << *f+1 << endl ;
else cout << "-1 -1\n" ;
}
}
}
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... |