QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#309950#8130. Yet Another Balanced Coloring Problemucup-team197#WA 14ms18628kbC++172.7kb2024-01-20 23:01:402024-01-20 23:01:41

Judging History

This is the latest submission verdict.

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-20 23:01:41]
  • Judged
  • Verdict: WA
  • Time: 14ms
  • Memory: 18628kb
  • [2024-01-20 23:01:40]
  • Submitted

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 ;
}

詳細信息

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)