Submission #626697

#	Time	Username	Problem	Language	Result	Execution time	Memory
626697		chonka	Park (BOI16_park)	C++17	100 / 100	385 ms	33612 KiB

park

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 2007 ;
const double inf = 5e9 + 4 ;

int n , q ;
ll w , h ;
struct el {
    ll x , y , r ;
};
el a[ MAXN ] ;

struct edge {
    int x , y ;
    double len ;
    edge ( ) { x = y = len = 0 ; }
    edge ( int _x , int _y , double _len ) {
        x = _x , y = _y ;
        len = _len ;
    }
};
vector < edge > v ;

int prv[ MAXN ] , rnk[ MAXN ] ;
double fst[ 5 ][ 5 ] ;
double mx[ 5 ][ 5 ] ;

int get ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = get ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}

void unite ( int x , int y ) {
    int k1 = get ( x ) , k2 = get ( y ) ;
    if ( k1 != k2 ) {
        if ( rnk[ k1 ] >= rnk[ k2 ] ) {
            rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
            prv[ k2 ] = k1 ;
        }
        else {
            prv[ k1 ] = k2 ;
        }
    }
}

void solve ( ) {
    cin >> n >> q ;
    cin >> w >> h ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y >> a[ i ].r ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j < i ; ++ j ) {
            double aux = ( a[ i ].x - a[ j ].x ) * ( a[ i ].x - a[ j ].x )
                + ( a[ i ].y - a[ j ].y ) * ( a[ i ].y - a[ j ].y ) ;
            aux = sqrt ( aux ) - a[ i ].r - a[ j ].r ;
            v.push_back ( edge ( i , j , aux ) ) ;
        }

        v.push_back ( edge ( i , n + 1 , a[ i ].y - a[ i ].r ) ) ;
        v.push_back ( edge ( i , n + 2 , ( w - a[ i ].x ) - a[ i ].r ) ) ;
        v.push_back ( edge ( i , n + 3 , ( h - a[ i ].y ) - a[ i ].r ) ) ;
        v.push_back ( edge ( i , n + 4 , a[ i ].x - a[ i ].r ) ) ;
    }
    for ( int i = 1 ; i <= n + 4 ; ++ i ) {
        prv[ i ] = -1 , rnk[ i ] = 0 ;
    }
    for ( int i = 1 ; i <= 4 ; ++ i ) {
        for ( int j = 1 ; j <= 4 ; ++ j ) {
            mx[ i ][ j ] = fst[ i ][ j ] = inf ;
        }
        fst[ i ][ i ] = 0 ;
    }
    auto cmp = [ & ] ( edge p1 , edge p2 ) {
        return ( p1.len < p2.len ) ;
    };
    sort ( v.begin ( ) , v.end ( ) , cmp ) ;
    for ( auto e : v ) {
        unite ( e.x , e.y ) ;
        for ( int i = 1 ; i <= 4 ; ++ i ) {
            for ( int j = i + 1 ; j <= 4 ; ++ j ) {
                if ( get ( n + i ) == get ( n + j ) ) {
                    fst[ i ][ j ] = min ( fst[ i ][ j ] , e.len ) ;
                    fst[ j ][ i ] = min ( fst[ j ][ i ] , e.len ) ;
                }
            }
        }
    }
    for ( int i = 1 ; i <= 4 ; ++ i ) {
        for ( int j = i + 1 ; j <= 4 ; ++ j ) {
            for ( int t = i ; t < j ; ++ t ) {
                for ( int z = 1 ; z <= 4 ; ++ z ) {
                    if ( i <= z && z < j ) { continue ; }
                    mx[ i ][ j ] = min ( mx[ i ][ j ] , fst[ t ][ z ] ) ;
                }
            }
        }
    }
    while ( q -- ) {
        double r ; int st ;
        cin >> r >> st ;
        r = 2 * r ;
        for ( int i = 1 ; i <= 4 ; ++ i ) {
            if ( mx[ min ( i , st ) ][ max ( i , st ) ] >= r ) {
                cout << i ;
            }
        }
        cout << "\n" ;
    }
}

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

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42