Submission #672478

#TimeUsernameProblemLanguageResultExecution timeMemory
672478CutebolBirthday gift (IZhO18_treearray)C++17
100 / 100
1118 ms102284 KiB
#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)

treearray.cpp: In function 'void fopn(std::string)':
treearray.cpp:5:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:5:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...