oj.uz

Submission #824479

# Submission time Handle Problem Language Result Execution time Memory
824479 2023-08-14T06:47:30 Z 반딧불(#10358) Sirtet (CCO19_day1problem2) C++17
0 / 25
 112 ms 35280 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);
    }
}

vector<pair<int, int> > link[1000002]; /// x번 집합이 k칸 내려갔을 때 y번 집합이 k+d칸까지 내려갈 수 있다면 (y, d) 삽입
int dist[1000002];
bool visited[1000002];

int ans[1000002];

struct dat{
    int x, d;
    dat(){}
    dat(int x, int d): x(x), d(d){}
    bool operator<(const dat &r)const{
        return d>r.d;
    }
};

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 j=1; j<=m; j++){
        int lastI = n+1, lastC = 0;
        for(int i=n; i>=1; i--){
            if(!board[get(i, j)]) continue;
            if(lastC == board[get(i, j)]) lastI = i;
            else{
                link[lastC].push_back(make_pair(board[get(i, j)], lastI-i-1));
                lastC = board[get(i, j)], lastI = i;
            }
        }
    }

    priority_queue<dat> pq;
    pq.push(dat(0, 0));
    while(!pq.empty()){
        dat tmp = pq.top(); pq.pop();
        if(visited[tmp.x]) continue;
        visited[tmp.x] = 1;
        dist[tmp.x] = tmp.d;
        //printf("dijkstra %d - %d\n", tmp.x, tmp.d);
        for(auto p: link[tmp.x]){
            pq.push(dat(p.first, tmp.d + p.second));
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!board[get(i, j)]) continue;
            int c = board[get(i, j)];
            ans[get(i+dist[c], j)] = c;
        }
    }

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

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

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23800 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 35280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23800 KB Output is correct
4 Incorrect 12 ms 23764 KB Output isn't correct
5 Halted 0 ms 0 KB -