oj.uz

Submission #542963

# Submission time Handle Problem Language Result Execution time Memory
542963 2022-03-28T14:42:06 Z chonka Capital City (JOI20_capital_city) C++
1 / 100
 714 ms 42804 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define MAXN 200007

int n , k ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
vector < int > col[ MAXN ] ;

int tot ;
int used[ MAXN ] , subtree[ MAXN ] , prv[ MAXN ] , mrk[ MAXN ] ;
bool added[ MAXN ] ;
vector < int > clist ;
int ans = MAXN ; 

void dfs ( int vertex , int lst , int ori ) {
    mrk[ vertex ] = ori ;
    ++ tot ;
    subtree[ vertex ] = 1 ;
    for ( auto x : v[ vertex ] ) {
        if ( x == lst || used[ x ] == 1 ) { continue ; }
        prv[ x ] = vertex ;
        dfs ( x , vertex , ori ) ;
        subtree[ vertex ] += subtree[ x ] ;
    }
}
int get_centroid ( int vertex , int lst ) {
    for ( auto x : v[ vertex ] ) {
        if ( x == lst || used[ x ] == 1 ) { continue ; }
        if ( 2 * subtree[ x ] > tot ) {
            return get_centroid ( x , vertex ) ;
        }
    }
    return vertex ;
}

queue < int > q ;

void decompose ( int vertex ) {
    tot = 0 , prv[ vertex ] = 0 ;
    dfs ( vertex , -1 , vertex ) ;
    vertex = get_centroid ( vertex , -1 ) ;
    tot = 0 , prv[ vertex ] = 0 ;
    dfs ( vertex , -1 , vertex ) ;
    
    bool ok = true ;
    for ( auto x : col[ a[ vertex ] ] ) {
        if ( mrk[ x ] != vertex ) {
            ok = false ;
            break ;
        }
        q.push ( x ) ;
    }
    clist.push_back ( a[ vertex ] ) ;
    added[ a[ vertex ] ] = true ;
    while ( q.empty ( ) == false ) {
        if ( ok == false ) { break ; }
        int x = q.front ( ) ;
        q.pop ( ) ;
        if ( prv[ x ] >= 1 ) {
            if ( added[ a[ prv[ x ] ] ] == false ) {
                for ( auto x : col[ a[ prv[ x ] ] ] ) {
                    if ( mrk[ x ] != vertex ) {
                        ok = false ;
                        break ;
                    }
                    q.push ( x ) ;
                }
                added[ a[ prv[ x ] ] ] = true ;
                clist.push_back ( a[ prv[ x ] ] ) ;
            }
        }
    }
    if ( ok == true ) {
        ans = min ( ans , (int)clist.size ( ) - 1 ) ;
    }
    for ( auto x : clist ) {
        added[ x ] = false ;
    }
    clist.clear ( ) ;
    used[ vertex ] = 1 ;
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == 0 ) {
            decompose ( x ) ;
        }
    }
}

void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i < n ; ++ i ) {
        int x , y ; cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        col[ a[ i ] ].push_back ( i ) ;
    }
}

void solve ( ) {
    decompose ( 1 ) ;
    cout << ans << "\n" ;
}

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9732 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9732 KB Output is correct
11 Correct 7 ms 9900 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9872 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 7 ms 9868 KB Output is correct
16 Correct 7 ms 9812 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 6 ms 9872 KB Output is correct
19 Correct 7 ms 9908 KB Output is correct
20 Incorrect 7 ms 9912 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 42424 KB Output is correct
2 Correct 217 ms 42780 KB Output is correct
3 Correct 560 ms 42072 KB Output is correct
4 Correct 189 ms 42804 KB Output is correct
5 Correct 535 ms 38852 KB Output is correct
6 Correct 179 ms 42736 KB Output is correct
7 Correct 564 ms 39204 KB Output is correct
8 Correct 185 ms 42604 KB Output is correct
9 Correct 643 ms 37480 KB Output is correct
10 Correct 628 ms 35072 KB Output is correct
11 Correct 663 ms 37928 KB Output is correct
12 Correct 714 ms 40536 KB Output is correct
13 Incorrect 621 ms 34596 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9732 KB Output is correct
11 Correct 7 ms 9900 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9872 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 7 ms 9868 KB Output is correct
16 Correct 7 ms 9812 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 6 ms 9872 KB Output is correct
19 Correct 7 ms 9908 KB Output is correct
20 Incorrect 7 ms 9912 KB Output isn't correct
21 Halted 0 ms 0 KB -