Submission #576263

#	Time	Username	Problem	Language	Result	Execution time	Memory
576263		chonka	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1097 ms	273668 KiB

bitaro

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 100007 ;
const int MAGIC = 330 ;

int n , m , q ;
vector < int > v[ MAXN ] ;
pair < int , int > ans[ MAXN ][ MAGIC ] ;
bool used[ MAXN ] ;

bool bad[ MAXN ] ;
pair < int , int > aux[ MAGIC ] ;
int ret[ MAXN ] ;
bool sel[ MAXN ] ;

void unite ( int host , int nw ) {
    int tp = 0 ;
    int pos1 , pos2 ;
    pos1 = pos2 = 0 ;
    while ( tp < MAGIC ) {
        while ( pos1 < MAGIC && sel[ ans[ host ][ pos1 ].first ] == true ) { ++ pos1 ; }
        while ( pos2 < MAGIC && sel[ ans[ nw ][ pos2 ].first ] == true ) { ++ pos2 ; }
        if ( pos1 == MAGIC ) {
            aux[ tp ++ ] = ans[ nw ][ pos2 ++ ] ;
            if ( aux[ tp - 1 ].second >= 0 ) {
                ++ aux[ tp - 1 ].second ;
            }
        }
        else if ( pos2 == MAGIC ) {
            aux[ tp ++ ] = ans[ host ][ pos1 ++ ] ;
        }
        else {
            int cand = ans[ nw ][ pos2 ].second ;
            if ( cand >= 0 ) { ++ cand ; }
            if ( ans[ host ][ pos1 ].second >= cand ) {
                aux[ tp ++ ] = ans[ host ][ pos1 ++ ] ;
            }
            else {
                aux[ tp ++ ] = ans[ nw ][ pos2 ++ ] ;
                if ( aux[ tp - 1 ].second >= 0 ) {
                    ++ aux[ tp - 1 ].second ;
                }
            }
        }
        sel[ aux[ tp - 1 ].first ] = true ;
    }
    for ( int i = 0 ; i < MAGIC ; ++ i ) {
        ans[ host ][ i ] = aux[ i ] ;
        sel[ aux[ i ].first ] = false ;
    }
}

void init ( int vertex ) {
    used[ vertex ] = true ;
    for ( int i = 0 ; i < MAGIC ; ++ i ) {
        ans[ vertex ][ i ] = { 0 , -1 } ;
    }
    ans[ vertex ][ 0 ] = { vertex , 0 } ;
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == false ) {
            init ( x ) ;
        }
        unite ( vertex , x ) ;
    }
}

void dfs ( int vertex ) {
    used[ vertex ] = true ;
    ret[ vertex ] = -1 ;
    if ( bad[ vertex ] == false ) { ret[ vertex ] = 0 ; }
    for ( auto x : v[ vertex ] ) {
        if ( used[ x ] == false ) {
            dfs ( x ) ;
        }
        if ( ret[ x ] >= 0 ) {
            ret[ vertex ] = max ( ret[ vertex ] , ret[ x ] + 1 ) ;
        }
    }
}

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

int hh[ MAXN ] ;

void solve ( ) {
    for ( int i = n ; i >= 1 ; -- i ) {
        if ( used[ i ] == false ) {
            init ( i ) ;
        }
    }
    while ( q -- ) {
        int ori , sz ;
        cin >> ori >> sz ;
        for ( int i = 0 ; i < sz ; ++ i ) {
            cin >> hh[ i ] ;
            bad[ hh[ i ] ] = true ;
        }
        if ( sz < MAGIC ) {
            bool fl = false ;
            for ( int i = 0 ; i < MAGIC ; ++ i ) {
                if ( ans[ ori ][ i ].second < 0 ) { break ; }
                if ( bad[ ans[ ori ][ i ].first ] == false ) {
                    fl = true ;
                    cout << ans[ ori ][ i ].second << "\n" ;
                    break ;
                }
            }
            if ( fl == false ) { cout << "-1\n" ; }
        }
        else {
            for ( int i = 1 ; i <= n ; ++ i ) {
                used[ i ] = false ;
            }
            dfs ( ori ) ;
            cout << ret[ ori ] << "\n" ;
        }
        for ( int i = 0 ; i < sz ; ++ i ) {
            bad[ hh[ i ] ] = false ;
        }
    }
}

int main ( ) {
    /// freopen ( "in.txt" , "r" , stdin ) ;
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t ;
    /// cin >> t ;
    t = 1 ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86