oj.uz

Submission #626697

# Submission time Handle Problem Language Result Execution time Memory
626697 2022-08-11T16:18:03 Z chonka Park (BOI16_park) C++17
100 / 100
 385 ms 33612 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 33320 KB Output is correct
2 Correct 322 ms 33312 KB Output is correct
3 Correct 335 ms 33384 KB Output is correct
4 Correct 322 ms 33392 KB Output is correct
5 Correct 324 ms 33316 KB Output is correct
6 Correct 341 ms 33416 KB Output is correct
7 Correct 305 ms 33320 KB Output is correct
8 Correct 288 ms 33324 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2232 KB Output is correct
2 Correct 48 ms 2068 KB Output is correct
3 Correct 54 ms 2076 KB Output is correct
4 Correct 55 ms 2156 KB Output is correct
5 Correct 60 ms 2144 KB Output is correct
6 Correct 60 ms 2184 KB Output is correct
7 Correct 45 ms 1760 KB Output is correct
8 Correct 45 ms 1704 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 33320 KB Output is correct
2 Correct 322 ms 33312 KB Output is correct
3 Correct 335 ms 33384 KB Output is correct
4 Correct 322 ms 33392 KB Output is correct
5 Correct 324 ms 33316 KB Output is correct
6 Correct 341 ms 33416 KB Output is correct
7 Correct 305 ms 33320 KB Output is correct
8 Correct 288 ms 33324 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 51 ms 2232 KB Output is correct
12 Correct 48 ms 2068 KB Output is correct
13 Correct 54 ms 2076 KB Output is correct
14 Correct 55 ms 2156 KB Output is correct
15 Correct 60 ms 2144 KB Output is correct
16 Correct 60 ms 2184 KB Output is correct
17 Correct 45 ms 1760 KB Output is correct
18 Correct 45 ms 1704 KB Output is correct
19 Correct 385 ms 33560 KB Output is correct
20 Correct 365 ms 33612 KB Output is correct
21 Correct 368 ms 33592 KB Output is correct
22 Correct 363 ms 33552 KB Output is correct
23 Correct 361 ms 33584 KB Output is correct
24 Correct 336 ms 33552 KB Output is correct