Submission #495971

#TimeUsernameProblemLanguageResultExecution timeMemory
495971vinnipuh01Birthday gift (IZhO18_treearray)C++17
0 / 100
5 ms4940 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> using namespace std; const long long oo = 1000000000000000000; long long int sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen ( "sum.in", "r", stdin ) */ int x, y, l, r, a[ 200001 ], type, par[ 200001 ][ 21 ], lg = 20; vector <int> v[ 200001 ], vv; int tin[ 200001 ], tout[ 200001 ], tmr, d[ 200001 ], t[ 800001 ]; void dfs( int u, int pr = 1 ) { par[ u ][ 0 ] = pr; vv.push_back( u ); tin[ u ] = ++tmr; for ( int i = 1; i <= lg; i ++ ) par[ u ][ i ] = par[ par[ u ][ i - 1 ] ][ i - 1 ]; for ( auto to : v[ u ] ) { if ( to != pr ) { d[ to ] = d[ u ] + 1; dfs( to, u ); } } tout[ u ] = tmr; } bool ok( int a, int b ) { return ( tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ] ); } int lca( int a, int b ) { if ( ok( a, b ) ) return a; if ( ok( b, a ) ) return b; for ( int i = lg; i >= 0; i -- ) { if ( !ok( par[ a ][ i ], b ) ) a = par[ a ][ i ]; } return par[ a ][ 0 ]; } void build( int v, int tl, int tr ) { if ( tl == tr ) { t[ v ] = a[ tl ]; return; } int mid = ( tl + tr ) / 2; build( v + v, tl, mid ); build( v + v + 1, mid + 1, tr ); t[ v ] = lca( t[ v + v ], t[ v + v + 1 ] ); } void upd( int v, int tl, int tr, int pos, int x ) { if ( tl > pos || tr < pos ) return; if ( tl == tr ) { t[ v ] = x; return; } int mid = ( tl + tr ) / 2; upd( v + v, tl, mid, pos, x ); upd( v + v + 1, mid + 1, tr, pos, x ); t[ v ] = lca( t[ v + v ], t[ v + v + 1 ] ); } void gett( int v, int tl, int tr, int l, int r ) { if ( tl > r || tr < l ) return; if ( tl >= l && tr <= r ) { if ( !num ) num = t[ v ]; else num = lca( num, t[ v ] ); return; } int mid = ( tl + tr ) / 2; gett( v + v, tl, mid ,l ,r ); gett( v + v + 1, mid + 1, tr, l, r ); } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand( time(0) ); int n, m, q; cin >> n >> m >> q; for ( int i = 1; i < n; i ++ ) { cin >> x >> y; v[ x ].push_back( y ); v[ y ].push_back( x ); } for ( int i = 1; i <= m; i ++ ) { cin >> a[ i ]; } dfs( 1 ); build( 1, 1, m ); int L, R, ll, rr; while ( q -- ) { cin >> type >> l >> r; if ( type == 2 ) { cin >> x; sum = 100; while ( sum -- ) { R = rand() % ( r - l + 1 ) + l; L = rand() % ( r - l + 1 ) + l; if ( L > R ) swap( L, R ); num = 0; gett( 1, 1, m, L, R ); if ( num == x ) break; } if ( num != x ) cout << "-1 -1\n"; else cout << L << " " << R << "\n"; } else { upd( 1, 1, m, l, r ); } } } /* CX 1 1 3 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 */

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:135:12: warning: unused variable 'll' [-Wunused-variable]
  135 |  int L, R, ll, rr;
      |            ^~
treearray.cpp:135:16: warning: unused variable 'rr' [-Wunused-variable]
  135 |  int L, R, ll, rr;
      |                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...