제출 #293143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293143		CaroLinda	Furniture (JOI20_furniture)	C++14	100 / 100	857 ms	117368 KiB

furniture

#include <bits/stdc++.h>

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

const int MAXN = 1010 ;
const int MAX = 1e6+100;

using namespace std ;

int N , M , Q ;
int qtdDist[ MAXN*3 ] ;
int grid[MAXN][MAXN] ;
vector<int> adj[MAX] , revAdj[MAX] ;
bool isOn[MAX] ;

int code(int i, int j) { return i*M + j ; }
bool valid(int i, int j) { return 0 <= min(i,j) && i < N && j < M ; }

void desliga(int x)
{
    if(!isOn[x]) return ;

    vector<int> fila ;

    //Desligando adj
    for(auto e : adj[x] )
    {
        if( x == revAdj[e][0] && sz(revAdj[e]) > 1 )  swap( revAdj[e][0] , revAdj[e][1] ) ;
        revAdj[e].pop_back() ;

        if( sz(revAdj[e]) == 0 ) fila.pb(e) ;

    }

    //Desligando revAdj
    for(auto e : revAdj[x])
    {
        if( x == adj[e][0] && sz(adj[e]) > 1 ) swap( adj[e][0] , adj[e][1] ) ;
        adj[e].pop_back() ;

        if( sz(adj[e]) == 0 ) fila.pb(e) ;

    }

    isOn[x] = false ;
    adj[x].clear() ;
    revAdj[x].clear() ;

    int i = x/M ;
    int j = x%M ;

    qtdDist[ i + j ]-- ;

    for(int i : fila )
        if( isOn[i] ) desliga(i) ;

}

int main()
{
    scanf("%d%d", &N , &M ) ;
    lp(i,0,N)
        lp(j,0,M)
        {
            scanf("%d", &grid[i][j] ) ;

            isOn[ code(i,j) ] = true ;
            qtdDist[ i + j ]++ ;

            int viz0 = -1, viz1 = -1, viz2 = -1, viz3 = -1 ;
            int idx = code(i,j) ;

            if( valid(i-1,j) ) viz0 = code(i-1,j) ;
            if( valid(i,j+1) ) viz1 = code(i,j+1) ;
            if( valid(i+1, j) ) viz2 = code(i+1,j) ;
            if( valid(i,j-1) ) viz3 = code(i,j-1) ;

            if( viz0 != -1 ) revAdj[ idx ].pb( viz0 ) ;
            if( viz3 != -1 ) revAdj[idx].pb( viz3 ) ;
            if( viz1 != -1 ) adj[idx].pb( viz1 ) ;
            if( viz2 != -1 ) adj[idx].pb( viz2 ) ;

        }

    lp(i,0,N)
        lp(j,0,M)
            if( grid[i][j] == 1 ) desliga(code(i,j)) ;

    scanf("%d", &Q ) ;


    for(int i = 1 , x , y ; i <= Q ; i++ )
    {
        scanf("%d%d", &x, &y ) ;
        x-- , y-- ;

        if( qtdDist[x+y] == 1 && isOn[ code(x,y) ] )
        {
            printf("0\n") ;
            continue ;
        }

        desliga(code(x,y)) ;
        printf("1\n") ;

    }

}

컴파일 시 표준 에러 (stderr) 메시지

furniture.cpp: In function 'int main()':
furniture.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%d%d", &N , &M ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~
furniture.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |             scanf("%d", &grid[i][j] ) ;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
furniture.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d", &Q ) ;
      |     ~~~~~^~~~~~~~~~~
furniture.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |         scanf("%d%d", &x, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95