QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331816#8055. Balanceucup-team197#WA 85ms17036kbC++176.6kb2024-02-18 19:57:082024-02-18 19:57:08

Judging History

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

  • [2024-02-18 19:57:08]
  • 评测
  • 测评结果：WA
  • 用时：85ms
  • 内存：17036kb
查看
  • [2024-02-18 19:57:08]
  • 提交

answer

#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 = 2e5 + 7 ;

int n , m ;
vector < pii > v[ MAXN ] ;
int vals[ MAXN ] ;
int edge[ MAXN ] ;

int Time ;
int num[ MAXN ] ;
int comp_id ;
vector < int > st ;

int dfs ( int x , int prv ) {
    int me = num[ x ] = ++ Time , e , y , top = me ;
    for ( auto foo : v[ x ] ) {
        if ( foo.se == prv ) { continue ; }
        tie ( y , e ) = foo ;
        if ( num[ y ] != 0 ) {
            top = min ( top , num[ y ] ) ;
            if ( num[ y ] < me ) { st.push_back ( e ) ; }
        }
        else {
            int si = st.size ( ) ;
            int up = dfs ( y , e ) ;
            top = min ( top , up ) ;
            if ( up == me ) {
                st.push_back ( e ) ;
                ++ comp_id ;
                for ( int i = si ; i < st.size ( ) ; ++ i ) {
                    edge[ st[ i ] ] = comp_id ;
                }
                st.resize ( si ) ;
            }
            else if ( up < me ) { st.push_back ( e ) ; }
            else { }
        }
    }
    return top ;
}

int prv[ MAXN ] , rnk[ MAXN ] , sz[ MAXN ] ;
pii edgelist[ MAXN ] ;

int get ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = get ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}

void unite ( int x , int y ) {
    int k1 = get ( x ) , k2 = get ( y ) ;
    if ( k1 == k2 ) { return ; }
    if ( rnk[ k1 ] < rnk[ k2 ] ) { swap ( k1 , k2 ) ; }
    rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
    prv[ k2 ] = k1 ;
    sz[ k1 ] += sz[ k2 ] ;
}

vector < int > gr[ MAXN ] ;
int subtree[ MAXN ] ;
bool dp_left[ MAXN ] , dp_right[ MAXN ] ;
int nxt_left[ MAXN ] , nxt_right[ MAXN ] ;
int win , spec_left , spec_right ;

void calc ( int x , int prv ) {
    subtree[ x ] = sz[ x ] ;
    for ( auto y : gr[ x ] ) {
        if ( y == prv ) { continue ; }
        calc ( y , x ) ;
        subtree[ x ] += subtree[ y ] ;
    }
    set < pii > possible_right ;
    for ( auto y : gr[ x ] ) {
        if ( y == prv ) { continue ; }
        if ( dp_left[ y ] == true && vals[ subtree[ x ] ] == vals[ subtree[ y ] + 1 ] ) {
            dp_left[ x ] = true ;
            nxt_left[ x ] = y ;
        }
        if ( dp_right[ y ] == true && vals[ n - subtree[ y ] ] == vals[ n - subtree[ x ] + 1 ] ) {
            dp_right[ x ] = true ;
            nxt_right[ x ] = y ;
        }
        if ( dp_right[ y ] == true ) { 
            possible_right.insert ( { subtree[ y ] , y } ) ;
        }
    }
    if ( sz[ x ] == subtree[ x ] ) {
        if ( vals[ subtree[ x ] ] == vals[ 1 ] ) { dp_left[ x ] = true ; }
        if ( vals[ n - subtree[ x ] + 1 ] == vals[ n ] ) { dp_right[ x ] = true ; }
    }
    /**
    printf ( "%d %d %d\n" , x , nxt_left[ x ] , nxt_right[ x ] ) ;
    if ( dp_left[ x ] == true ) { printf ( "%d left\n" , x ) ; }
    if ( dp_right[ x ] == true ) { printf ( "%d right\n" , x ) ; }
    **/
    for ( auto y : gr[ x ] ) {
        if ( y == prv ) { continue ; }
        if ( dp_right[ y ] == true ) { 
            possible_right.erase ( { subtree[ y ] , y } ) ;
        }
        if ( dp_left[ y ] == true ) {
            auto it = possible_right.end ( ) ;
            if ( it != possible_right.begin ( ) ) { 
                -- it ;
                int other_size = it->fi ;
                if ( vals[ subtree[ y ] + 1 ] == vals[ n - other_size ] ) {
                    win = x ;
                    spec_left = y , spec_right = it->se ;
                }
            }
        }
        if ( dp_right[ y ] == true ) { 
            possible_right.insert ( { subtree[ y ] , y } ) ;
        }
    }
}

int ans[ MAXN ] ;

void fill ( int x , int prv , int col ) {
    ans[ x ] = col ;
    for ( auto y : gr[ x ] ) {
        if ( y == prv ) { continue ; }
        fill ( y , x , col ) ;
    }
}

void mrk ( int x , int prv , int type ) {
    if ( x <= 0 ) { return ; }
    int act = 0 ;
    if ( type == -1 ) { act = vals[ subtree[ x ] ] ; }
    else { act = vals[ n - subtree[ x ] + 1 ] ; }
    ans[ x ] = act ;
    // printf ( "mrk %d %d %d %d\n" , x , prv , type , act ) ;
    for ( auto y : gr[ x ] ) {
        if ( y == prv ) { continue ; }
        if ( y == nxt_left[ x ] && type == -1 ) { continue ; }
        if ( y == nxt_right[ x ] && type == 1 ) { continue ; }
        fill ( y , x , act ) ;
    }
    if ( type == -1 && nxt_left[ x ] > 0 ) { mrk ( nxt_left[ x ] , x , type ) ; }
    if ( type == 1 && nxt_right[ x ] > 0 ) { mrk ( nxt_right[ x ] , x , type ) ; }
}

void solve ( ) {
    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        v[ i ].clear ( ) ;
        gr[ i ].clear ( ) ;
        num[ i ] = 0 ;
        dp_left[ i ] = dp_right[ i ] = false ;
        nxt_left[ i ] = nxt_right[ i ] = 0 ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        edge[ i ] = 0 ;
    }
    for ( int i = 1 , x , y ; i <= m ; ++ i ) {
        cin >> x >> y ;
        edgelist[ i ] = { x , y } ;
        v[ x ].push_back ( { y , i } ) ;
        v[ y ].push_back ( { x , i } ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> vals[ i ] ;
    }
    sort ( vals + 1 , vals + n + 1 ) ;
    Time = comp_id = 0 ;
    st.clear ( ) ;
    dfs ( 1 , -1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        prv[ i ] = -1 , rnk[ i ] = 0 ;
        sz[ i ] = 1 ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        if ( edge[ i ] > 0 ) {
            unite ( edgelist[ i ].fi , edgelist[ i ].se ) ;
        }
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        if ( edge[ i ] == 0 ) {
            int x = get ( edgelist[ i ].fi ) , y = get ( edgelist[ i ].se ) ;
            // printf ( "bridge %d %d\n" , edgelist[ i ].fi , edgelist[ i ].se ) ;
            gr[ x ].push_back ( y ) ;
            gr[ y ].push_back ( x ) ;
        }
    }
    int root = get ( 1 ) ;
    win = -1 ;
    calc ( root , -1 ) ;
    if ( dp_left[ root ] == true ) {
        spec_left = nxt_left[ root ] ;
        win = root ;
    }
    if ( win == -1 ) {
        cout << "No\n" ;
        return ;
    }
    cout << "Yes\n" ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        ans[ i ] = vals[ subtree[ spec_left ] + 1 ] ;
    }
    mrk ( spec_left , win , -1 ) ;
    mrk ( spec_right , win , 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cout << ans[ get ( i ) ] << " " ;
    }
    cout << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

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

output:

Yes
5 4 3 2 1 
No
Yes
2 2 2 3 1 
Yes
2 2 1 1 1 
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 85ms
memory: 17036kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

output:

Yes
2 2 3 1 
No
Yes
1 1 1 
No
No
Yes
2 1 1 1 
No
No
Yes
1 1 
Yes
1 1 
Yes
1 1 
Yes
1 1 1 1 
No
Yes
1 1 1 1 1 
No
Yes
1 1 1 
Yes
2 2 
Yes
1 1 1 1 1 
Yes
2 1 
No
Yes
1 1 
Yes
1 1 1 
Yes
1 1 
Yes
1 1 1 1 
Yes
1 1 
Yes
2 2 2 2 2 
Yes
1 1 1 1 1 
Yes
1 1 
Yes
1 1 1 2 
No
Yes
1 1 
No
Yes
1 1 
No
No
No
Yes
...

result:

wrong answer ans finds an answer, but out doesn't (test case 15)
English 繁體中文 简体中文

伺服器時間: 2024-12-02 21:35:10 | 開源專案