oj.uz

Submission #824407

# Submission time Handle Problem Language Result Execution time Memory
824407 2023-08-14T05:35:32 Z 반딧불(#10358) Sirtet (CCO19_day1problem2) C++17
0 / 25
 2000 ms 7316 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};

int n, m;
int board[1000002], ccnt;

inline int get(int x, int y){
    return (x-1)*m+y;
}

void dfs(int x, int y, int c){
    board[get(x, y)] = c;
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty=y+yy[d];
        if(board[get(tx, ty)] != -1) continue;
        dfs(tx, ty, c);
    }
}

bool visited[1000002], seen[1000002];
bool ableToMoveDown(int x, int y, int c){
    if(x==n || (board[get(x+1, y)] && board[get(x+1, y)] != c)) return false;
    visited[get(x, y)] = 1;
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(board[get(tx, ty)] != c || visited[get(tx, ty)]) continue;
        if(!ableToMoveDown(tx, ty, c)) return false;
    }
    return true;
}

bool visited2[1000002];
void getVec(int x, int y, int c, vector<pair<int, int> > &v){
    visited2[get(x, y)] = 1;
    v.push_back(make_pair(x, y));
    for(int d=0; d<4; d++){
        int tx=x+xx[d], ty=y+yy[d];
        if(board[get(tx, ty)] == c && !visited2[get(tx, ty)]) getVec(tx, ty, c, v);
    }
}

void moveDown(int x, int y){
    int c = board[get(x, y)];
    vector<pair<int, int> > v;
    getVec(x, y, c, v);
    for(pair<int, int> p: v) board[get(p.first, p.second)] = 0;
    for(pair<int, int> p: v) board[get(p.first+1, p.second)] = c;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            scanf(" %c", &c);
            if(c=='#') board[get(i, j)] = -1;
        }
    }

    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(board[get(i, j)] == -1) dfs(i, j, ++ccnt);

//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++){
//            printf("%d", board[get(i, j)]);
//        }
//        puts("");
//    }

    while(1){
        bool found = false;
        for(int i=1; i<=n*m; i++) visited[i] = visited2[i] = seen[i] = 0;
        for(int i=n; i>=1; i--){
            for(int j=1; j<=m; j++){
                if(!board[get(i, j)] || seen[board[get(i, j)]]) continue;
                int c = board[get(i, j)];
                seen[c] = 1;
                if(ableToMoveDown(i, j, c)) found = 1, moveDown(i, j);
            }
        }
        if(!found) break;

//        for(int i=1; i<=n; i++){
//            for(int j=1; j<=m; j++) printf("%c", board[get(i, j)] ? '#' : '.');
//            puts("");
//        }
//        puts("");
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) printf("%c", board[get(i, j)] ? '#' : '.');
        puts("");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 7316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Halted 0 ms 0 KB -