oj.uz

Submission #225564

# Submission time Handle Problem Language Result Execution time Memory
225564 2020-04-20T21:19:12 Z CaroLinda Building Skyscrapers (CEOI19_skyscrapers) C++14
8 / 100
 834 ms 53636 KB 
#include <bits/stdc++.h>

#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAX = 1e6+10 ;
const int MAXN = 1e5+10 ;

using namespace std ;

int N , T , idx ;
int X[MAXN] , Y[MAXN] , vet[MAXN] , pai[MAX] , pai_aux[MAXN] ;
int dx[8] = { 1,-1,0,0, 1,-1,1,-1 } , dy[8] = { 0,0,1,-1, -1,1, 1, -1} ;
int dx_cyclic[8] = { -1 , -1 , 0 , 1 , 1 ,1 , 0, -1 } , dy_cyclic[8] = { 0 , -1 , -1 , -1, 0 , 1 , 1 ,1  } ;
pii id[MAX] ;
bool is_full[MAX] , reachable[MAX] , marc[MAXN] ;
map< pii , int > mp ;
priority_queue<int> fila ;
vector<int> ans ;
vector<int> componente[MAX] ;

// ------------------------------------------------

bool cmp_maior_x( int i , int j ) { return X[i] > X[j] ; }
bool cmp_menor_x ( int i , int j ) { return X[i] < X[j] ; }
bool cmp_maior_y(int i , int j) { return Y[i] > Y[j] ; }
bool cmp_menor_y ( int i , int j ) { return Y[i] < Y[j] ; }

int get_code(int x, int y) { return mp.find( mk(x,y) )->ss ; }

int find(int x)
{
    if( x == pai[x] ) return x ;
    return pai[x] = find( pai[x] ) ;
}


int group[8] , belong[8] ;
bool identify_articulation(int name)
{
    bool latter = false ;

    for(int i = 0  , nx , ny; i < 8 ; i++ )
    {
        nx = dx_cyclic[i] + X[name] ;
        ny = dy_cyclic[i] + Y[name] ;

        if( is_full[ get_code(nx,ny) ]  ) { group[i] =0 , latter = false ; belong[i] = -1 ;continue ; }

        if( latter || i == 1 || i == 3 || i == 5 || i == 7 ) group[i] = 0 , belong[i] = belong[i-1] ;
        else
        {
            group[i] = find( get_code(nx,ny) ) ;
            belong[i] = i ;
            latter= true ;
        }

    }

    if( belong[7] != -1 && belong[0] != -1 && group[ belong[7] ] == group[ belong[0] ] )
        group[ belong[7] ] = 0 ;

    sort( group , group+8  ) ;
    for(int i = 1 ; i< 8 ; i++ )
        if( group[i-1] != 0 && ( group[i] == group[i-1] ) ) return true ;

    return false ;
}

bool identify_infinity(int name)
{
    bool ans = false ;

    for(int i = 0 ; i < 4 ; i++ )
    {

        int code = get_code( dx[i] + X[name] , dy[i] + Y[name] ) ;
        code = find(code) ;
        ans |= reachable[code] ;

    }

    return ans ;

}
bool check(int i) { return ( !identify_articulation(i) ) && identify_infinity(i) ; }

inline void to_change(int name)
{

    for(int i = 0 ; i < 8 ; i++ )
    {

        int nx = X[name] + dx[i] ;
        int ny = Y[name] + dy[i] ;
        int code = get_code( nx, ny ) ;

        if( is_full[code] && !marc[code] && check(code) )
        {
            fila.push(code);
            marc[code] = true ;
        }

    }

}

bool join(int a, int b, bool ok = false )
{

    a = find(a) ;
    b = find(b) ;

    if(a==b) return false ;

    if( componente[a].size() > componente[b].size() ) swap( a , b  );

    pai[a] = b ;
    reachable[b] |= reachable[a] ;

    for(int i : componente[a] )
    {
        componente[b].pb(i) ;
        if( ok ) to_change(i) ;
    }
    componente[a].clear() ;

    return true ;

}

int find_aux(int x)
{
    if( x == pai_aux[x] ) return x ;
    return pai_aux[x] = find_aux( pai_aux[x] ) ;
}
inline void join_aux(int a, int b)
{
    a = find_aux(a) ;
    b = find_aux(b) ;

    if( rand() % 2 ) swap(a,b) ;

    pai_aux[a] = b ;

}

int main()
{
    scanf("%d%d", &N , &T ) ;
    lp(i,1,N+1)
    {
        scanf("%d%d", &X[i] , &Y[i]) ;
        mp.insert( mk( mk( X[i] , Y[i] ) , i ) ) ;
        is_full[i] = true ;
        vet[i] = pai_aux[i] = i ;
    }

    idx = N ;

    lp(i,1,N+1)
    {
        for(int j = 0 ; j < 8 ; j++ )
        {

            int nx = dx[j] + X[i] ;
            int ny = dy[j] + Y[i] ;

            if( mp.find( mk(nx,ny) ) == mp.end() ) mp.insert( mk( mk(nx,ny) , ++idx ) ) ;

            if( is_full[ get_code(nx,ny) ] ) join_aux( i , get_code(nx,ny) ) ;

        }
    }

    lp(i,2,N+1)
        if( find_aux(i) != find_aux(1) ) {  printf("NO\n") ; return 0 ; }

    for(auto p : mp )
    {
        pai[ p.ss ] = p.ss ;
        componente[p.ss].pb( p.ss ) ;
    }

    // Get reachability to inifinity -----------

    sort( vet+1, vet+1+N, cmp_menor_x ) ;

    for(int i = 1 ; i <= N ; i++ )
    {
        if( X[ vet[i] ] > X[ vet[1] ] ) break ;

        int code = get_code( X[ vet[i] ] - 1 , Y[ vet[i] ] ) ;
        reachable[ code ] = true ;

    }

    sort( vet+1, vet+1+N, cmp_maior_x ) ;
    for(int i = 1 ; i <= N ; i++ )
    {

        if( X[ vet[i] ] < X[ vet[1] ] ) break ;

        int code = get_code( X[ vet[i] ] + 1 , Y[ vet[i] ] ) ;
        reachable[code] = true ;

    }
    sort( vet+1, vet+1+N, cmp_menor_y ) ;
    lp(i,1,N+1)
    {

        if( Y[ vet[i] ] > Y[ vet[1] ] ) break ;

        int code = get_code(X[ vet[i] ] , Y[ vet[i] ] - 1 ) ;
        reachable[code] = true ;

    }
    sort( vet+1, vet+1+N , cmp_maior_y ) ;
    lp(i,1,N+1)
    {
        if( Y[ vet[i] ] < Y[ vet[1] ] ) break ;

        int code = get_code( X[ vet[i] ] , Y[ vet[i] ] + 1  ) ;
        reachable[code] = true ;
    }

    // ---------------------------------------------

    for(auto p : mp )
    {

        if( is_full[p.ss] ) continue ;

        for(int i = 0 , nx , ny ; i < 4 ; i++ )
        {
            nx = dx[i] + p.ff.ff ;
            ny = dy[i] + p.ff.ss ;

            if( is_full[ get_code(nx,ny) ] ) continue ;

            join( get_code(nx,ny) , p.ss ) ;

        }

    }


    lp(i,1,N+1)
        if( check(i) ) fila.push( i ) , marc[i] = true ;

    while( !fila.empty() )
    {

        int best_id = fila.top() ;
        fila.pop() ;

        if( !check(best_id) ) { marc[best_id] = false ;  continue ; }

      //  debug("Entrei em %d\n" , best_id ) ;

        ans.pb( best_id ) ;
        is_full[best_id] = false ;

        for(int i = 0 , nx , ny ; i < 4 ; i++ )
        {
            nx = dx[i] + X[best_id] ;
            ny = dy[i] + Y[ best_id ] ;
            int code = get_code( nx,ny ) ;

            if( is_full[ code ] ) continue ;

            join( code, best_id ) ;

        }

        to_change(best_id) ;

    }

    printf("YES\n") ;
    reverse(all(ans)) ;
    for(int i : ans ) printf("%d\n" , i ) ;

}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N , &T ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~
skyscrapers.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &X[i] , &Y[i]) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB ans=YES N=1
2 Correct 18 ms 23808 KB ans=YES N=4
3 Correct 17 ms 23808 KB ans=NO N=4
4 Correct 21 ms 23808 KB ans=YES N=5
5 Correct 18 ms 23808 KB ans=YES N=9
6 Correct 18 ms 23808 KB ans=YES N=5
7 Correct 18 ms 23808 KB ans=NO N=9
8 Correct 18 ms 23808 KB ans=NO N=10
9 Correct 19 ms 23808 KB ans=YES N=10
10 Correct 21 ms 23936 KB ans=YES N=10
11 Correct 17 ms 23808 KB ans=YES N=10
12 Correct 20 ms 23808 KB ans=YES N=9
13 Correct 18 ms 23936 KB ans=YES N=9
14 Correct 19 ms 23808 KB ans=YES N=8
15 Correct 18 ms 23808 KB ans=YES N=8
16 Correct 18 ms 23808 KB ans=NO N=2

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB ans=YES N=1
2 Correct 18 ms 23808 KB ans=YES N=4
3 Correct 17 ms 23808 KB ans=NO N=4
4 Correct 21 ms 23808 KB ans=YES N=5
5 Correct 18 ms 23808 KB ans=YES N=9
6 Correct 18 ms 23808 KB ans=YES N=5
7 Correct 18 ms 23808 KB ans=NO N=9
8 Correct 18 ms 23808 KB ans=NO N=10
9 Correct 19 ms 23808 KB ans=YES N=10
10 Correct 21 ms 23936 KB ans=YES N=10
11 Correct 17 ms 23808 KB ans=YES N=10
12 Correct 20 ms 23808 KB ans=YES N=9
13 Correct 18 ms 23936 KB ans=YES N=9
14 Correct 19 ms 23808 KB ans=YES N=8
15 Correct 18 ms 23808 KB ans=YES N=8
16 Correct 18 ms 23808 KB ans=NO N=2
17 Correct 17 ms 23808 KB ans=YES N=17
18 Incorrect 17 ms 23808 KB Full cells must be connected
19 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB ans=YES N=1
2 Correct 18 ms 23808 KB ans=YES N=4
3 Correct 17 ms 23808 KB ans=NO N=4
4 Correct 21 ms 23808 KB ans=YES N=5
5 Correct 18 ms 23808 KB ans=YES N=9
6 Correct 18 ms 23808 KB ans=YES N=5
7 Correct 18 ms 23808 KB ans=NO N=9
8 Correct 18 ms 23808 KB ans=NO N=10
9 Correct 19 ms 23808 KB ans=YES N=10
10 Correct 21 ms 23936 KB ans=YES N=10
11 Correct 17 ms 23808 KB ans=YES N=10
12 Correct 20 ms 23808 KB ans=YES N=9
13 Correct 18 ms 23936 KB ans=YES N=9
14 Correct 19 ms 23808 KB ans=YES N=8
15 Correct 18 ms 23808 KB ans=YES N=8
16 Correct 18 ms 23808 KB ans=NO N=2
17 Correct 17 ms 23808 KB ans=YES N=17
18 Incorrect 17 ms 23808 KB Full cells must be connected
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24960 KB ans=NO N=1934
2 Correct 23 ms 24192 KB ans=NO N=1965
3 Incorrect 31 ms 24192 KB Contestant's solution is not lexicographically largest at index 1710 (1738 vs 1174)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB ans=YES N=1
2 Correct 18 ms 23808 KB ans=YES N=4
3 Correct 17 ms 23808 KB ans=NO N=4
4 Correct 21 ms 23808 KB ans=YES N=5
5 Correct 18 ms 23808 KB ans=YES N=9
6 Correct 18 ms 23808 KB ans=YES N=5
7 Correct 18 ms 23808 KB ans=NO N=9
8 Correct 18 ms 23808 KB ans=NO N=10
9 Correct 19 ms 23808 KB ans=YES N=10
10 Correct 21 ms 23936 KB ans=YES N=10
11 Correct 17 ms 23808 KB ans=YES N=10
12 Correct 20 ms 23808 KB ans=YES N=9
13 Correct 18 ms 23936 KB ans=YES N=9
14 Correct 19 ms 23808 KB ans=YES N=8
15 Correct 18 ms 23808 KB ans=YES N=8
16 Correct 18 ms 23808 KB ans=NO N=2
17 Correct 17 ms 23808 KB ans=YES N=17
18 Incorrect 17 ms 23808 KB Full cells must be connected
19 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 32096 KB ans=NO N=66151
2 Correct 408 ms 53636 KB ans=NO N=64333
3 Incorrect 834 ms 33888 KB Contestant's solution is not lexicographically largest at index 69273 (66979 vs 66485)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24960 KB ans=NO N=1934
2 Correct 23 ms 24192 KB ans=NO N=1965
3 Incorrect 31 ms 24192 KB Contestant's solution is not lexicographically largest at index 1710 (1738 vs 1174)
4 Halted 0 ms 0 KB -