oj.uz

답안 #607229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
607229 2022-07-26T13:39:52 Z chonka Min-max tree (BOI18_minmaxtree) C++
58 / 100
 169 ms 50604 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 ] ;

priority_queue < pair < int , int > > q ;

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 ] += 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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15680 KB Output is correct
2 Correct 11 ms 15656 KB Output is correct
3 Correct 11 ms 15700 KB Output is correct
4 Correct 9 ms 15696 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 30004 KB Output is correct
2 Correct 154 ms 26176 KB Output is correct
3 Correct 146 ms 28148 KB Output is correct
4 Correct 163 ms 31004 KB Output is correct
5 Correct 155 ms 27628 KB Output is correct
6 Correct 142 ms 26820 KB Output is correct
7 Correct 142 ms 26136 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 23568 KB Output is correct
2 Correct 117 ms 23636 KB Output is correct
3 Correct 84 ms 26972 KB Output is correct
4 Correct 81 ms 28728 KB Output is correct
5 Correct 93 ms 24568 KB Output is correct
6 Correct 87 ms 24980 KB Output is correct
7 Correct 90 ms 23788 KB Output is correct
8 Correct 94 ms 23708 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15680 KB Output is correct
2 Correct 11 ms 15656 KB Output is correct
3 Correct 11 ms 15700 KB Output is correct
4 Correct 9 ms 15696 KB Output is correct
5 Correct 156 ms 30004 KB Output is correct
6 Correct 154 ms 26176 KB Output is correct
7 Correct 146 ms 28148 KB Output is correct
8 Correct 163 ms 31004 KB Output is correct
9 Correct 155 ms 27628 KB Output is correct
10 Correct 142 ms 26820 KB Output is correct
11 Correct 142 ms 26136 KB Output is correct
12 Correct 100 ms 23568 KB Output is correct
13 Correct 117 ms 23636 KB Output is correct
14 Correct 84 ms 26972 KB Output is correct
15 Correct 81 ms 28728 KB Output is correct
16 Correct 93 ms 24568 KB Output is correct
17 Correct 87 ms 24980 KB Output is correct
18 Correct 90 ms 23788 KB Output is correct
19 Correct 94 ms 23708 KB Output is correct
20 Runtime error 169 ms 50604 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -