QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99829#6322. ForestrySortingWA 968ms102384kbC++208.9kb2023-04-23 20:18:462023-04-23 20:18:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-23 20:18:50]
  • 评测
  • 测评结果:WA
  • 用时:968ms
  • 内存:102384kb
  • [2023-04-23 20:18:46]
  • 提交

answer

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

const int MAXN = 3e5 + 7 ;
const int MOD = 998244353 ;

ll pw2[ MAXN ] ;

struct node {
    ll val , ways ;
    ll tot_ways , spec ;
    ll prior ;
    int cnt ;
    ll mul_lazy ;
    node *pl , *pr ;
    node ( ) {
        val = ways = tot_ways = spec = prior = mul_lazy = 0 ;
        cnt = 0 ;
    }
    node ( ll ori ) {
        val = spec = ori ;
        ways = tot_ways = 1 ;
        cnt = 1 ;
        prior = rng ( ) ;
        mul_lazy = 1 ;
        pl = pr = nullptr ;
    }
};


void push_lazy ( node *w ) {
    if ( w == nullptr ) { return ; }
    w->spec = ( w->spec * w->mul_lazy ) % MOD ;
    w->tot_ways = ( w->tot_ways * w->mul_lazy ) % MOD ;
    w->ways = ( w->ways * w->mul_lazy ) % MOD ;
    if ( w->pl != nullptr ) {
        w->pl->mul_lazy = ( w->pl->mul_lazy * w->mul_lazy ) % MOD ;
    }
    if ( w->pr != nullptr ) {
        w->pr->mul_lazy = ( w->pr->mul_lazy * w->mul_lazy ) % MOD ;
    }
    w->mul_lazy = 1 ;
}

void update ( node *w ) {
    if ( w == nullptr ) { return ; }
    push_lazy ( w ) ;
    w->cnt = 1 ;
    w->tot_ways = w->ways ;
    w->spec = ( w->ways * w->val ) % MOD ;
    if ( w->pl != nullptr ) {
        push_lazy ( w->pl ) ;
        w->cnt = w->cnt + w->pl->cnt ;
        w->tot_ways = ( w->tot_ways + w->pl->tot_ways ) % MOD ;
        w->spec = ( w->spec + w->pl->spec ) % MOD ;
    }
    if ( w->pr != nullptr ) {
        push_lazy ( w->pr ) ;
        w->cnt = w->cnt + w->pr->cnt ;
        w->tot_ways = ( w->tot_ways + w->pr->tot_ways ) % MOD ;
        w->spec = ( w->spec + w->pr->spec ) % MOD ;
    }
}


pair < node* , node* > split ( node* w , ll sr ) {
    push_lazy ( w ) ;
    if ( w == nullptr ) {
        return { nullptr , nullptr } ;
    }
    if ( w->val <= sr ) {
        auto [ ret1 , ret2 ] = split ( w->pr , sr ) ;
        push_lazy ( ret1 ) ; push_lazy ( ret2 ) ;
        w->pr = ret1 ;
        update ( w ) ;
        return { w , ret2 } ;
    }
    else {
        auto [ ret1 , ret2 ] = split ( w->pl , sr ) ;
        push_lazy ( ret1 ) ; push_lazy ( ret2 ) ;
        w->pl = ret2 ;
        update ( w ) ;
        return { ret1 , w } ;
    }
}

node* merge ( node* l , node *r ) {
    push_lazy ( l ) ;
    push_lazy ( r ) ;
    if ( l == nullptr ) {
        return r ;
    }
    if ( r == nullptr ) {
        return l ;
    }
    if ( l->prior >= r->prior ) {
        auto ret = merge ( l->pr , r ) ;
        push_lazy ( ret ) ;
        l->pr = ret ;
        update ( l ) ;
        return l ;
    }
    else {
        auto ret = merge ( l , r->pl ) ;
        push_lazy ( ret ) ;
        r->pl = ret ;
        update ( r ) ;
        return r ;
    }
}

ll get_all ( node *w , ll sr ) {
    push_lazy ( w ) ;
    if ( w == nullptr ) { return 0 ; }
    if ( sr <= w->val ) {
        ll ret = get_all ( w->pl , sr ) ;
        ret = ( ret + w->ways ) % MOD ;
        if ( w->pr != nullptr ) {
            push_lazy ( w->pr ) ;
            ret = ( ret + w->pr->tot_ways ) % MOD ;
        }
        return ret ;
    }
    else {
        return get_all ( w->pr , sr ) ;
    }
}

int n ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
node *root[ MAXN ] ;
int subtree[ MAXN ] ;
vector < node* > nw ;

void dfs ( node *w , node *big , bool fl ) {
    push_lazy ( w ) ;
    if ( w == nullptr ) { return ; }
    ll ways = get_all ( big , w->val ) ;
    // printf ( "query returns %lld\n" , ways ) ;
    node *aux = new node ( w->val ) ;
    aux->ways = aux->tot_ways = ( w->ways * ways ) % MOD ;
    aux->spec = ( aux->val * ways ) % MOD ;
    // printf ( "%d --> %lld  %lld\n" , aux->val , aux->ways , aux->spec ) ;
    nw.push_back ( aux ) ;
    if ( fl == false ) {
        node *foo = new node ( w->val ) ;
        foo->ways = foo->tot_ways = ( w->ways * big->tot_ways ) % MOD ;
        foo->spec = ( ( ( w->val * w->ways ) % MOD ) * big->tot_ways ) % MOD ;
        // printf ( "add %d %lld %lld\n" , foo->val , foo->ways , foo->spec ) ;
        nw.push_back ( foo ) ;
    }
    dfs ( w->pl , big , fl ) ;
    dfs ( w->pr , big , fl ) ;
}

struct elem {
    ll val , ways ;
    elem ( ) { val = ways = 0 ; }
    elem ( int _val , ll _ways ) {
        val = _val , ways = _ways ;
    }
};

vector < elem > all_small ;

void extr ( node *w ) {
    push_lazy ( w ) ;
    if ( w == nullptr ) { return ; }
    extr ( w->pl ) ;
    all_small.push_back ( elem ( w->val , w->ways ) ) ;
    extr ( w->pr ) ;
}

void printout ( node *w ) {
    push_lazy ( w ) ;
    if ( w == nullptr ) { return ; }
    printout ( w->pl ) ;
    // printf ( "val = %d, ways = %lld, spec = %lld\n" , w->val , w->ways , ( w->ways * w->val ) % MOD ) ;
    printout ( w->pr ) ;
}

bool direct_upd ( node *w , ll sr , ll add_ways , ll add_spec ) {
    push_lazy ( w ) ;
    if ( w == nullptr ) { return false ; }
    // printf ( "%d %lld %lld\n" , w->cnt , w->val , sr ) ;
    if ( w->val == sr ) {
        w->ways = ( w->ways + add_ways ) % MOD ;
        w->tot_ways = ( w->tot_ways + add_ways ) % MOD ;
        w->spec = ( w->spec + add_spec ) % MOD ;
        return true ;
    }
    if ( w->val < sr ) {
        bool ret = direct_upd ( w->pr , sr , add_ways , add_spec ) ;
        update ( w ) ;
        return ret ;
    }
    else {
        bool ret = direct_upd ( w->pl , sr , add_ways , add_spec ) ;
        update ( w ) ;
        return ret ;
    }
}

void add_num ( node * &wh , node *cand ) {
    if ( direct_upd ( wh , cand->val , cand->ways , cand->spec ) == true ) { return ; }
    node *lft , *rght ;
    tie ( lft , rght ) = split ( wh , cand->val ) ;
    lft = merge ( lft , cand ) ;
    wh = merge ( lft , rght ) ;    
}


node* unite ( node *big , node *small , bool fl ) {
    push_lazy ( big ) ;
    push_lazy ( small ) ;
    nw.clear ( ) ;
    dfs ( small , big , fl ) ;
    all_small.clear ( ) ;
    extr ( small ) ;
    int sz = all_small.size ( ) ;
    int lst = 0 ;
    ll hh_mul = 0 ;
    for ( int i = 0 ; i < sz ; ++ i ) {
        hh_mul = ( hh_mul + all_small[ i ].ways ) % MOD ;
    }
    // printf ( "--- %lld\n" , hh_mul ) ;
    for ( int i = 0 ; i < sz ; ++ i ) {
        node *lft , *rght , *mid ;
        tie ( lft , rght ) = split ( big , lst - 1 ) ;
        tie ( mid , rght ) = split ( rght , all_small[ i ].val - 1 ) ;
        
        push_lazy ( mid ) ;
        // printf ( "range between %d and %d by %lld\n" , lst - 1 , all_small[ i ].val - 1 , hh_mul + fl ) ;
        if ( mid != nullptr ) {
            if ( fl == false ) { mid->mul_lazy = hh_mul ; }
            else { mid->mul_lazy = ( hh_mul + small->tot_ways ) % MOD ; }
            push_lazy ( mid ) ;
        }
        rght = merge ( mid , rght ) ;
        big = merge ( lft , rght ) ;

        hh_mul = ( hh_mul + MOD - all_small[ i ].ways ) % MOD ;
        lst = all_small[ i ].val ;
    }
    if ( fl == true ) {
        node *lft , *rght ;
        tie ( lft , rght ) = split ( big , lst - 1 ) ;
        push_lazy ( rght ) ;
        if ( rght != nullptr ) { 
            rght->mul_lazy = small->tot_ways ;
            push_lazy ( rght ) ;
        }
        big = merge ( lft , rght ) ;
    }
    for ( auto hh : nw ) {
        add_num ( big , hh ) ;
        /**
        node *lft , *rght ;
        tie ( lft , rght ) = split ( big , hh->val ) ;
        lft = merge ( lft , hh ) ;
        big = merge ( lft , rght ) ;
        **/
    }
    return big ;
}

ll ans = 0 ;

void dfs ( int x , int prv ) {
    root[ x ] = new node ( a[ x ] ) ;
    subtree[ x ] = 1 ;
    for ( auto y : v[ x ] ) {
        if ( y == prv ) { continue ; }
        dfs ( y , x ) ;
        // printf ( "uniting parent %d with child %d\n" , x , y ) ;
        if ( subtree[ x ] >= subtree[ y ] ) {
            root[ x ] = unite ( root[ x ] , root[ y ] , true ) ;
        }
        else {
            root[ x ] = unite ( root[ y ] , root[ x ] , false ) ;
        }
        node *foo = nullptr ;
        tie ( root[ x ] , foo ) = split ( root[ x ] , a[ x ] ) ;
        // printout ( root[ x ] ) ;
        subtree[ x ] += subtree[ y ] ;
    }
    push_lazy ( root[ x ] ) ;
    assert ( root[ x ]->tot_ways == pw2[ subtree[ x ] - 1 ] ) ;
    ans = ( ans + root[ x ]->spec * pw2[ max ( n - subtree[ x ] - 1 , 0 ) ] ) % MOD ;
    // printf ( "end %d --> %d %lld\n" , x , root[ x ]->tot_ways , root[ x ]->spec * pw2[ max ( n - subtree[ x ] - 1 , 0 ) ] ) ;
}

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    pw2[ 0 ] = 1 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        pw2[ i ] = ( pw2[ i - 1 ] * 2 ) % MOD ;
    }
    for ( int i = 1 , x , y ; i < n ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        root[ i ] = nullptr ;
    }
    dfs ( 1 , -1 ) ;
    cout << ans << "\n" ;
}


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

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 15844kb

input:

4
1 2 3 4
1 2
2 4
3 2

output:

44

result:

ok 1 number(s): "44"

Test #2:

score: 0
Accepted
time: 5ms
memory: 15692kb

input:

5
3 5 6 5 1
4 1
2 3
3 5
1 3

output:

154

result:

ok 1 number(s): "154"

Test #3:

score: -100
Wrong Answer
time: 968ms
memory: 102384kb

input:

278989
864394090 384799247 186936242 598547507 962916136 540758021 158527118 688236322 682301622 948660645 881768181 481432818 557201870 794956026 205262301 920739629 141926922 990361777 818811172 150579096 1032726 328924563 638044961 21740781 484574329 737977343 113738003 345289940 363021157 582495...

output:

730359960

result:

wrong answer 1st numbers differ - expected: '434293031', found: '730359960'