oj.uz

Submission #607241

# Submission time Handle Problem Language Result Execution time Memory
607241 2022-07-26T13:49:52 Z chonka Min-max tree (BOI18_minmaxtree) C++
58 / 100
 205 ms 50572 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 = 140007 ;
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 ] ;

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 ) {
        srt.push_back ( { cnt[ i ] , i } ) ;
    }
    sort ( srt.begin ( ) , srt.end ( ) ) ;
    for ( auto [ foo , wh ] : srt ) {
        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 ] ;
        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:155:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |     for ( auto [ foo , wh ] : srt ) {
      |                ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15700 KB Output is correct
2 Correct 8 ms 15688 KB Output is correct
3 Correct 7 ms 15656 KB Output is correct
4 Correct 7 ms 15700 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 29984 KB Output is correct
2 Correct 143 ms 26248 KB Output is correct
3 Correct 126 ms 28128 KB Output is correct
4 Correct 150 ms 31004 KB Output is correct
5 Correct 123 ms 27648 KB Output is correct
6 Correct 121 ms 26896 KB Output is correct
7 Correct 106 ms 26156 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 23544 KB Output is correct
2 Correct 76 ms 23584 KB Output is correct
3 Correct 85 ms 27020 KB Output is correct
4 Correct 79 ms 28680 KB Output is correct
5 Correct 83 ms 24400 KB Output is correct
6 Correct 99 ms 25040 KB Output is correct
7 Correct 85 ms 23820 KB Output is correct
8 Correct 83 ms 23800 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15700 KB Output is correct
2 Correct 8 ms 15688 KB Output is correct
3 Correct 7 ms 15656 KB Output is correct
4 Correct 7 ms 15700 KB Output is correct
5 Correct 130 ms 29984 KB Output is correct
6 Correct 143 ms 26248 KB Output is correct
7 Correct 126 ms 28128 KB Output is correct
8 Correct 150 ms 31004 KB Output is correct
9 Correct 123 ms 27648 KB Output is correct
10 Correct 121 ms 26896 KB Output is correct
11 Correct 106 ms 26156 KB Output is correct
12 Correct 76 ms 23544 KB Output is correct
13 Correct 76 ms 23584 KB Output is correct
14 Correct 85 ms 27020 KB Output is correct
15 Correct 79 ms 28680 KB Output is correct
16 Correct 83 ms 24400 KB Output is correct
17 Correct 99 ms 25040 KB Output is correct
18 Correct 85 ms 23820 KB Output is correct
19 Correct 83 ms 23800 KB Output is correct
20 Runtime error 205 ms 50572 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -