QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#309898#8130. Yet Another Balanced Coloring Problemucup-team197#WA 8ms18408kbC++172.5kb2024-01-20 22:18:322024-01-20 22:18:32

Judging History

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

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

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

vector < int > gr[ MAXN ] ;

void dfs ( int x , int hh ) {
    if ( v[ hh ][ x ].empty ( ) == true ) {
        ord[ hh ].push_back ( x ) ;
    }
    for ( auto y : v[ hh ][ x ] ) {
        dfs ( y , hh ) ;
    }
}

int ans[ MAXN ] ;

void mrk ( int x , int prv , int col ) {
    ans[ x ] = col ;
    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 ;
    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 ) ;
    }
    ord[ 0 ].clear ( ) , ord[ 1 ].clear ( ) ;
    dfs ( n , 0 ) ;
    dfs ( m , 1 ) ;

    for ( int i = 0 ; i <= max ( n , m ) ; ++ i ) {
        gr[ i ].clear ( ) ;
        ans[ i ] = 0 ;
    }
    int k = ord[ 0 ].size ( ) ;
    int ori = k ;
    if ( ( k % 2 ) == 1 ) { 
        ord[ 0 ].push_back ( 0 ) ;
        ord[ 1 ].push_back ( 0 ) ;
        ++ k ;
    }
    for ( int i = 0 ; i < k ; i += 2 ) {
        int nxt = ( i + 1 ) % k ;
        gr[ ord[ 0 ][ i ] ].push_back ( ord[ 0 ][ nxt ] ) ;
        gr[ ord[ 0 ][ nxt ] ].push_back ( ord[ 0 ][ i ] ) ;

        gr[ ord[ 1 ][ i ] ].push_back ( ord[ 1 ][ nxt ] ) ;
        gr[ ord[ 1 ][ nxt ] ].push_back ( ord[ 1 ][ i ] ) ;
    }
    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: 0ms
memory: 17692kb

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
BRR

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 8ms
memory: 18408kb

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
BRBRB
BRRBRB
BRB
BRBRB
BRBRR
BBRR
BRBR
BRRBRBB
BRBRBRB
BRR
BRBRBR
BBR
BRBRBRB
BRRRBB
BBRR
BBR
BRBRR
BRR
BBRBR
BBRRB
BRBR
BRBRR
BRB
BRBRR
BBRR
BRBRBR
BBRRBR
BRBR
BRBRBR
BBRRBR
BRBRR
BRBRBR
BRRBBR
BRBRBR
BBR
BBRR
BRR
BRB
BRBRB
BBRR
BRBRBR
BRR
BRBRR
BRR
BRBRBR
BRBRRB
BRR
BRBRBR
BRB
BRB
BBRR
BRBRR
...

result:

wrong answer charge of vertex 8 in tree 2 violates range (test case 4)