QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309935#8130. Yet Another Balanced Coloring Problemucup-team197#WA 8ms19860kbC++172.6kb2024-01-20 22:50:162024-01-20 22:50:17

Judging History

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

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

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 ].empty ( ) == true ) { 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: 0ms
memory: 19860kb

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: 8ms
memory: 19468kb

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
BRRBB
BBR
BRRBB
BBRRB
BRBR
BRRBB
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 7 in tree 2 violates range (test case 18)