oj.uz

Submission #607248

# Submission time Handle Problem Language Result Execution time Memory
607248 2022-07-26T13:58:59 Z chonka Min-max tree (BOI18_minmaxtree) C++
100 / 100
 198 ms 27740 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define fi first 
#define se second 
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 70007 ;
const int inf = 1e9 + 7 ;

int n ;
vector < int > v[ MAXN ] ;

int prv[ MAXN ] , lvl[ MAXN ] ;
int subtree[ MAXN ] , heavy[ MAXN ] ;
int pos_in_tree[ MAXN ] , root[ MAXN ] ;

struct query {
    int type , x , y ;
    int val ;
};
query qlist[ MAXN ] ;

void dfs ( int x , int lst ) {
    subtree[ x ] = 1 ;
    int mx = -1 ;
    for ( auto y : v[ x ] ) {
        if ( y == lst ) { continue ; }
        prv[ y ] = x ;
        lvl[ y ] = lvl[ x ] + 1 ;
        dfs ( y , x ) ;
        subtree[ x ] += subtree[ y ] ;
        if ( mx < subtree[ y ] ) {
            mx = subtree[ y ] ;
            heavy[ x ] = y ;
        }
    }
}

struct node {
    pair < int , int > mn , mx ;
    node ( ) {
        mn = { -inf , 0 } ;
        mx = { inf , 0 } ;
    }
};
node tr[ 4 * MAXN ] ;

void update ( int where , int IL , int IR , int CURL , int CURR , int sr , int id , int type ) {
    if ( IL > IR || CURL > CURR ) { return ; }
    if ( IR < CURL || CURR < IL ) { return ; }
    if ( CURL <= IL && IR <= CURR ) {
        if ( type == 0 ) {
            if ( tr[ where ].mn.fi < sr ) {
                tr[ where ].mn = { sr , id } ;
            }
        }
        else {
            if ( sr < tr[ where ].mx.fi ) {
                tr[ where ].mx = { sr , id } ;
            }
        }
        return ;
    }
    int mid = ( IL + IR ) / 2 ;
    update ( 2 * where , IL , mid , CURL , CURR , sr , id , type ) ;
    update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , sr , id , type ) ;
}

node query ( int where , int IL , int IR , int pos ) {
    if ( IR < pos || pos < IL ) { return node ( ) ; }
    if ( IL == IR ) { return tr[ where ] ; }
    node ret = node ( ) ;
    int mid = ( IL + IR ) / 2 ;
    if ( pos <= mid ) { ret = query ( 2 * where , IL , mid , pos ) ; }
    else { ret = query ( 2 * where + 1 , mid + 1 , IR , pos ) ; }
    if ( ret.mn.fi < tr[ where ].mn.fi ) {
        ret.mn = tr[ where ].mn ;
    }
    if ( ret.mx.fi > tr[ where ].mx.fi ) {
        ret.mx = tr[ where ].mx ;
    }
    return ret ;
}

int cnt[ MAXN ] ;


vector < int > cont[ MAXN ] ;
int ans[ MAXN ] ;
int idle[ MAXN ] ;
vector < pair < int , int > > srt ;
pair < int , int > hh[ MAXN ] ;

priority_queue < pair < int , int > > pq ;
bool done[ MAXN ] ;

void solve ( ) {
    cin >> n ;
    for ( int i = 1 , x , y ; i < n ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    dfs ( 1 , -1 ) ;
    int tp = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( i == 1 || heavy[ prv[ i ] ] != i ) {
            int x = i ;
            while ( x != 0 ) {
                root[ x ] = i ;
                pos_in_tree[ x ] = ++ tp ;
                x = heavy[ x ] ;
            }
        }
    }
    int q ;
    cin >> q ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        char c ;
        cin >> c ;
        if ( c == 'm' ) { qlist[ i ].type = 0 ; }
        else { qlist[ i ].type = 1 ; }

        cin >> qlist[ i ].x >> qlist[ i ].y >> qlist[ i ].val ;
        int x = qlist[ i ].x , y = qlist[ i ].y ;

        while ( root[ x ] != root[ y ] ) {
            if ( lvl[ root[ x ] ] < lvl[ root[ y ] ] ) { swap ( x , y ) ; }
            update ( 1 , 1 , n , pos_in_tree[ root[ x ] ] , pos_in_tree[ x ] , qlist[ i ].val , i , qlist[ i ].type ) ;
            x = prv[ root[ x ] ] ;
        }
        if ( pos_in_tree[ x ] > pos_in_tree[ y ] ) { swap ( x , y ) ; }
        update ( 1 , 1 , n , pos_in_tree[ x ] + 1 , pos_in_tree[ y ] , qlist[ i ].val , i , qlist[ i ].type ) ;
    }
    for ( int i = 2 ; i <= n ; ++ i ) {
        node ret = query ( 1 , 1 , n , pos_in_tree[ i ] ) ;
        hh[ i ] = { ret.mn.se , ret.mx.se } ;
        ++ cnt[ ret.mn.se ] ;
        ++ cnt[ ret.mx.se ] ;
        if ( ret.mn.se > 0 ) {
            cont[ ret.mn.se ].push_back ( i ) ;
            idle[ i ] = ret.mn.fi ;
        }
        if ( ret.mx.se > 0 ) {
            cont[ ret.mx.se ].push_back ( i ) ;
            idle[ i ] = ret.mx.fi ;
        }
    }
    cnt[ 0 ] += MAXN ; 
    for ( int i = 1 ; i <= n ; ++ i ) {
        ans[ i ] = -inf ;
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        pq.push ( { -cnt[ i ] , i } ) ;
        srt.push_back ( { cnt[ i ] , i } ) ;
    }
    while ( pq.empty ( ) == false ) {
        auto [ foo , wh ] = pq.top ( ) ;
        pq.pop ( ) ;
        foo = -foo ;
        if ( cnt[ wh ] != foo || done[ wh ] == true ) { continue ; }
        int mx_oth = -1 , aux = 0 ;
        
        for ( auto cand : cont[ wh ] ) {
            if ( ans[ cand ] == -inf ) {
                int oth = hh[ cand ].first + hh[ cand ].second - wh ;
                if ( mx_oth < cnt[ oth ] ) {
                    mx_oth = cnt[ oth ] ;
                    aux = cand ;
                }
            }
        }
        ans[ aux ] = qlist[ wh ].val ;
        int oth = hh[ aux ].first + hh[ aux ].second - wh ;

        -- cnt[ oth ] ;
        pq.push ( { -cnt[ oth ] , oth } ) ;
        
        done[ wh ] = true ;
        cnt[ wh ] = max ( cnt[ wh ] , MAXN ) ;
    }
    for ( int i = 2 ; i <= n ; ++ i ) {
        cout << prv[ i ] << " " << i << " " ;
        if ( ans[ i ] != -inf ) { cout << ans[ i ] << "\n" ; }
        else { cout << idle[ i ] << "\n" ; }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

Compilation message

minmaxtree.cpp: In function 'void solve()':
minmaxtree.cpp:159:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |         auto [ foo , wh ] = pq.top ( ) ;
      |              ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8020 KB Output is correct
3 Correct 4 ms 8020 KB Output is correct
4 Correct 4 ms 8020 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 23004 KB Output is correct
2 Correct 146 ms 19116 KB Output is correct
3 Correct 118 ms 20984 KB Output is correct
4 Correct 146 ms 24000 KB Output is correct
5 Correct 198 ms 20572 KB Output is correct
6 Correct 184 ms 19832 KB Output is correct
7 Correct 119 ms 19068 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 16116 KB Output is correct
2 Correct 114 ms 16192 KB Output is correct
3 Correct 116 ms 19512 KB Output is correct
4 Correct 77 ms 21252 KB Output is correct
5 Correct 98 ms 17020 KB Output is correct
6 Correct 100 ms 17580 KB Output is correct
7 Correct 86 ms 16340 KB Output is correct
8 Correct 116 ms 16376 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 4 ms 8020 KB Output is correct
3 Correct 4 ms 8020 KB Output is correct
4 Correct 4 ms 8020 KB Output is correct
5 Correct 168 ms 23004 KB Output is correct
6 Correct 146 ms 19116 KB Output is correct
7 Correct 118 ms 20984 KB Output is correct
8 Correct 146 ms 24000 KB Output is correct
9 Correct 198 ms 20572 KB Output is correct
10 Correct 184 ms 19832 KB Output is correct
11 Correct 119 ms 19068 KB Output is correct
12 Correct 107 ms 16116 KB Output is correct
13 Correct 114 ms 16192 KB Output is correct
14 Correct 116 ms 19512 KB Output is correct
15 Correct 77 ms 21252 KB Output is correct
16 Correct 98 ms 17020 KB Output is correct
17 Correct 100 ms 17580 KB Output is correct
18 Correct 86 ms 16340 KB Output is correct
19 Correct 116 ms 16376 KB Output is correct
20 Correct 160 ms 19328 KB Output is correct
21 Correct 139 ms 20460 KB Output is correct
22 Correct 146 ms 20472 KB Output is correct
23 Correct 150 ms 20432 KB Output is correct
24 Correct 139 ms 25824 KB Output is correct
25 Correct 141 ms 27740 KB Output is correct
26 Correct 130 ms 26872 KB Output is correct
27 Correct 168 ms 25184 KB Output is correct
28 Correct 150 ms 22132 KB Output is correct
29 Correct 153 ms 22280 KB Output is correct
30 Correct 136 ms 21084 KB Output is correct
31 Correct 162 ms 21100 KB Output is correct
32 Correct 143 ms 21636 KB Output is correct
33 Correct 147 ms 21096 KB Output is correct
34 Correct 161 ms 21040 KB Output is correct
35 Correct 136 ms 20632 KB Output is correct