QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309929#8130. Yet Another Balanced Coloring Problemucup-team197#WA 6ms19292kbC++172.6kb2024-01-20 22:45:092024-01-20 22:45:10

Judging History

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

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

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 ) {
        // ord[ hh ].push_back ( x ) ;
        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 {
            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 ][ 1 ] != lft[ 1 ][ 1 ] ) {
            gr[ lft[ 0 ][ 1 ] ].push_back ( lft[ 1 ][ 1 ] ) ;
            gr[ lft[ 1 ][ 1 ] ].push_back ( lft[ 0 ][ 1 ] ) ;
        }
    }
    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: 19292kb

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: 6ms
memory: 19128kb

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
BRBRBB
BRBR
BBR
BRBRB
BBR
BRBRB
BBRRB
BRBR
BRBRB
BRB
BRBRB
BRBR
BRBRBR
BBRBRR
BRRB
BBRBRR
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 10 in tree 1 violates range (test case 15)