QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309950#8130. Yet Another Balanced Coloring Problemucup-team197#WA 14ms18628kbC++172.7kb2024-01-20 23:01:402024-01-20 23:01:41

Judging History

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

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-20 23:01:41]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:18628kb
  • [2024-01-20 23:01:40]
  • 提交

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 , k ;
vector < int > v[ 2 ][ MAXN ] ;
vector < int > gr[ MAXN ] ;

int lft[ 2 ][ MAXN ] ;

void dfs ( int x , int hh ) {
    lft[ hh ][ x ] = 0 ;
    if ( v[ hh ][ x ].empty ( ) == true ) {
        lft[ hh ][ x ] = x ;
        k = max ( k , x ) ;
    }
    for ( auto y : v[ hh ][ x ] ) {
        dfs ( y , hh ) ;
        if ( lft[ hh ][ x ] > 0 && lft[ hh ][ y ] > 0 ) {
            gr[ lft[ hh ][ x ] ].push_back ( lft[ hh ][ y ] ) ;
            gr[ lft[ hh ][ y ] ].push_back ( lft[ hh ][ x ] ) ;
            lft[ hh ][ x ] = 0 ;
        }
        else if ( lft[ hh ][ x ] == 0 && lft[ hh ][ y ] > 0 ) {
            lft[ hh ][ x ] = lft[ hh ][ y ] ;
        }
    }
}

int ans[ MAXN ] ;


void mrk ( int x , int prv , int col ) {
    ans[ x ] = col ;
    if ( gr[ x ].size ( ) == 0 ) { return ; }
    if ( gr[ x ].size ( ) == 1 && prv != -1 ) { return ; }
    if ( prv == gr[ x ][ 0 ] ) {
        if ( ans[ gr[ x ][ 1 ] ] == 0 ) { 
            mrk ( gr[ x ][ 1 ] , x , 3 - col ) ;
        }
    }
    else {
        if ( ans[ gr[ x ][ 0 ] ] == 0 ) { 
            mrk ( gr[ x ][ 0 ] , x , 3 - col ) ;
        }
    }
}

void solve ( ) {
    cin >> n >> m ;
    k = 0 ;
    for ( int i = 0 ; i <= max ( n , m ) ; ++ i ) {
        v[ 0 ][ i ].clear ( ) , v[ 1 ][ i ].clear ( ) ;
    }
    for ( int i = 1 , x ; i < n ; ++ i ) {
        cin >> x ;
        v[ 0 ][ x ].push_back ( i ) ;
    }
    for ( int i = 1 , x ; i < m ; ++ i ) {
        cin >> x ;
        v[ 1 ][ x ].push_back ( i ) ;
    }
    for ( int i = 0 ; i <= max ( n , m ) ; ++ i ) {
        gr[ i ].clear ( ) ;
        ans[ i ] = 0 ;
    }

    dfs ( n , 0 ) ;
    dfs ( m , 1 ) ;
    int ori = k ;
    /**
    if ( ( k % 2 ) == 1 ) {
        if ( lft[ 0 ][ n ] != lft[ 1 ][ m ] ) {
            gr[ lft[ 0 ][ n ] ].push_back ( lft[ 1 ][ m ] ) ;
            gr[ lft[ 1 ][ m ] ].push_back ( lft[ 0 ][ n ] ) ;
        }
    }
    **/
    for ( int i = 1 ; i <= ori ; ++ i ) {
        if ( ans[ i ] == 0 ) {
            mrk ( i , -1 , 1 ) ;
        }
    }
    for ( int i = 1 ; i <= ori ; ++ i ) {
        if ( ans[ i ] == 1 ) { cout << "B" ; }
        else { cout << "R" ; }
    }
    cout << "\n" ;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 18628kb

input:

2
7 7
5 5 6 6 7 7
5 6 5 6 7 7
5 4
4 4 5 5
4 4 4

output:

BRRB
BRB

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 14ms
memory: 18320kb

input:

10000
6 6
5 5 5 5 6
5 6 6 6 6
9 6
7 9 7 7 6 8 9 9
6 6 6 6 6
9 8
9 9 8 7 7 8 8 9
7 7 8 7 7 7 8
6 10
4 5 5 6 6
4 6 5 7 8 9 8 9 10
6 9
6 6 6 6 6
6 9 7 8 8 9 9 9
8 9
8 6 6 7 6 7 8
7 9 7 6 7 8 9 9
9 8
6 7 7 5 8 8 8 9
7 5 6 5 8 7 8
8 7
6 6 5 5 6 7 8
5 7 6 6 7 7
9 9
8 9 8 8 8 8 9 9
9 9 8 8 9 9 8 9
9 8
8 8 ...

output:

BRBR
BRRBB
BRBBRR
BBR
BRBRB
BBRBR
BBRR
BRBR
BBRBRBR
BRBRBRB
BRB
BRBRBR
BBR
BRBRBRB
BRRRBB
BRBR
BBR
BRBRB
BBR
BRBRB
BBRRB
BRBR
BRBRB
BRB
BRBRB
BBRR
BRBRBR
BBRBRR
BRRB
BRBRBR
BRRBRB
BRBRB
BRBRBR
BRBRBR
BBRRBR
BRB
BBRR
BBR
BBR
BRBRB
BBRR
BRBRBR
BBR
BBRBR
BRB
BRBRBR
BRRBBR
BBR
BRBRBR
BBR
BRB
BRBR
BRBRB
...

result:

wrong answer charge of vertex 6 in tree 2 violates range (test case 32)