結果

問題 No.2470 Gemini Tree(Ver.Jadeite)
コンテスト
ユーザー Yerin Jung
提出日時 2023-09-23 23:54:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 5,000 ms
コード長 5,025 bytes
コンパイル時間 2,060 ms
コンパイル使用メモリ 178,572 KB
実行使用メモリ 21,016 KB
最終ジャッジ日時 2024-07-16 23:44:31
合計ジャッジ時間 8,833 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 1e5 + 7 ;
const ll inf = 1e18 ;

int n , q ;
string s ;
int type[ MAXN ] ;
struct edge {
    int x , y , cost ;
};
edge a[ MAXN ] ;
vector < int > v[ MAXN ] ;
pii upd_list[ MAXN ] ;
ll ans[ MAXN ] ;

int lvl[ MAXN ] , subtree[ MAXN ] ;

void init ( int x , int prv ) {
    subtree[ x ] = 1 ;
    for ( auto y : v[ x ] ) {
        if ( y == prv ) { continue ; }
        lvl[ y ] = lvl[ x ] + 1 ;
        init ( y , x ) ;
        subtree[ x ] += subtree[ y ] ;
    }
}

int targ ;
int st[ MAXN ] , en[ MAXN ] ;
vector < int > ord ;

int spec_parent[ MAXN ] ;
int sub_sm[ MAXN ] ;
int rvpos[ MAXN ] ;

void setup ( int x , int prv , int hh ) {
    spec_parent[ x ] = hh ;
    if ( subtree[ x ] == targ ) {
        ord.push_back ( x ) ;
        st[ x ] = ord.size ( ) ;
        rvpos[ x ] = st[ x ] ;
        hh = x ;
    }
    else {
        st[ x ] = ord.size ( ) + 1 ;
    }
    sub_sm[ x ] = type[ x ] ;
    for ( auto y : v[ x ] ) {
        if ( y == prv ) { continue ; }
        setup ( y , x , hh ) ;
        sub_sm[ x ] += sub_sm[ y ] ;
    }
    en[ x ] = ord.size ( ) ;
}

class Tree {
public :
    ll tr[ 4 * MAXN ] , lazy[ 4 * MAXN ] ;
    void init ( int w , int l , int r ) {
        tr[ w ] = lazy[ w ] = 0 ;
        if ( l == r ) { return ; }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
    }
    void absorb ( int w , ll x ) {
        tr[ w ] += x ;
        lazy[ w ] += x ;
    }
    void push_lazy ( int w , int l , int r ) {
        if ( l != r ) { 
            absorb ( 2 * w , lazy[ w ] ) ;
            absorb ( 2 * w + 1 , lazy[ w ] ) ;
        }
        lazy[ w ] = 0 ;
    }
    void update ( int w , int l , int r , int st , int en , ll add ) {
        if ( l > r || st > en ) { return ; }
        if ( r < st || en < l ) { return ; }
        if ( st <= l && r <= en ) {
            absorb ( w , add ) ;
            return ;
        }
        push_lazy ( w , l , r ) ;
        int mid = ( l + r ) / 2 ;
        update ( 2 * w , l , mid , st , en , add ) ;
        update ( 2 * w + 1 , mid + 1 , r , st , en , add ) ;
        tr[ w ] = min ( tr[ 2 * w ] , tr[ 2 * w + 1 ] ) ;
    }
    ll query ( ) { return tr[ 1 ] ; }
};
Tree w ;

int spec_cnt ;

void add ( int id , ll val ) {
    int up = a[ id ].x , down = a[ id ].y ;
    if ( lvl[ up ] > lvl[ down ] ) { swap ( up , down ) ; }
    if ( spec_parent[ down ] != -1 ) {
        int wh = rvpos[ spec_parent[ down ] ] ;
        w.update ( 1 , 1 , spec_cnt , wh , wh , val * ( subtree[ down ] - sub_sm[ down ] ) ) ;
    }
    w.update ( 1 , 1 , spec_cnt , st[ down ] , en[ down ] , val * ( targ - sub_sm[ down ] ) ) ;

    if ( spec_parent[ down ] == -1 ) {
        w.update ( 1 , 1 , spec_cnt , 1 , st[ down ] - 1 , val * sub_sm[ down ] ) ;
        w.update ( 1 , 1 , spec_cnt , en[ down ] + 1 , spec_cnt , val * sub_sm[ down ] ) ;
    }
    else {
        int wh = rvpos[ spec_parent[ down ] ] ;        
        w.update ( 1 , 1 , spec_cnt , 1 , wh - 1 , val * sub_sm[ down ] ) ;
        w.update ( 1 , 1 , spec_cnt , wh + 1 , st[ down ] - 1 , val * sub_sm[ down ] ) ;
        w.update ( 1 , 1 , spec_cnt , en[ down ] + 1 , spec_cnt , val * sub_sm[ down ] ) ;
    }
}

void calc ( ) {
    ord.clear ( ) ;
    targ = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        targ += type[ i ] ;
    }
    setup ( 1 , -1 , -1 ) ;
    spec_cnt = ord.size ( ) ;
    if ( spec_cnt == 0 ) { return ; }
    w.init ( 1 , 1 , spec_cnt ) ;
    for ( int i = 1 ; i < n ; ++ i ) {
        if ( a[ i ].cost > 0 ) {
            add ( i , a[ i ].cost ) ;
        }
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        add ( upd_list[ i ].fi , upd_list[ i ].se ) ;
        ans[ i ] = min ( ans[ i ] , w.query ( ) ) ;
    }
}

void solve ( ) {
    cin >> n ;
    cin >> s ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( s[ i - 1 ] == 'G' ) { type[ i ] = 1 ; }
        else { type[ i ] = 0 ; }
    }
    for ( int i = 1 ; i < n ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y >> a[ i ].cost ;
        v[ a[ i ].x ].push_back ( a[ i ].y ) ;
        v[ a[ i ].y ].push_back ( a[ i ].x ) ;
    }
    cin >> q ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        cin >> upd_list[ i ].fi >> upd_list[ i ].se ;
        ans[ i ] = inf ;
    }
    init ( 1 , -1 ) ;

    calc ( ) ;
    for ( int i = 1 ; i <= n ; ++ i ) { type[ i ] ^= 1 ; }
    calc ( ) ;

    for ( int i = 1 ; i <= q ; ++ i ) {
        cout << ans[ i ] << "\n" ;
    }
}

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