oj.uz

Submission #607234

# Submission time Handle Problem Language Result Execution time Memory
607234 2022-07-26T13:43:37 Z chonka Min-max tree (BOI18_minmaxtree) C++
58 / 100
 163 ms 50584 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 ( 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:154:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  154 |     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 15700 KB Output is correct
3 Correct 9 ms 15692 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 138 ms 30036 KB Output is correct
2 Correct 141 ms 26176 KB Output is correct
3 Correct 125 ms 28172 KB Output is correct
4 Correct 111 ms 31004 KB Output is correct
5 Correct 122 ms 27576 KB Output is correct
6 Correct 116 ms 26944 KB Output is correct
7 Correct 106 ms 26112 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 23492 KB Output is correct
2 Correct 89 ms 23556 KB Output is correct
3 Correct 78 ms 27020 KB Output is correct
4 Correct 88 ms 28844 KB Output is correct
5 Correct 82 ms 24416 KB Output is correct
6 Correct 83 ms 24912 KB Output is correct
7 Correct 87 ms 23828 KB Output is correct
8 Correct 83 ms 23728 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 15700 KB Output is correct
3 Correct 9 ms 15692 KB Output is correct
4 Correct 7 ms 15700 KB Output is correct
5 Correct 138 ms 30036 KB Output is correct
6 Correct 141 ms 26176 KB Output is correct
7 Correct 125 ms 28172 KB Output is correct
8 Correct 111 ms 31004 KB Output is correct
9 Correct 122 ms 27576 KB Output is correct
10 Correct 116 ms 26944 KB Output is correct
11 Correct 106 ms 26112 KB Output is correct
12 Correct 76 ms 23492 KB Output is correct
13 Correct 89 ms 23556 KB Output is correct
14 Correct 78 ms 27020 KB Output is correct
15 Correct 88 ms 28844 KB Output is correct
16 Correct 82 ms 24416 KB Output is correct
17 Correct 83 ms 24912 KB Output is correct
18 Correct 87 ms 23828 KB Output is correct
19 Correct 83 ms 23728 KB Output is correct
20 Runtime error 163 ms 50584 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -