oj.uz

Submission #824694

# Submission time Handle Problem Language Result Execution time Memory
824694 2023-08-14T08:53:36 Z 이성호(#10360) Sirtet (CCO19_day1problem2) C++17
6 / 25
 145 ms 81532 KB 
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
using namespace std;
int N, M; //(i, j) -> (i - 1) * M + (j - 1)
struct UnionFind
{
    vector<int> par;
    UnionFind(int n)
    {
        par.resize(n+1);
        iota(par.begin(), par.end(), 0);
    };
    int fin(int v)
    {
        return v == par[v] ? v : (par[v] = fin(par[v]));
    }
    void uni(int u, int v)
    {
        par[fin(u)] = fin(v);
    }
};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
vector<string> c;
int num(int i, int j)
{
    return (i - 1) * M + (j - 1);
}
pair<int, int> inv(int i)
{
    return make_pair(i / M + 1, i % M + 1);
}
const int inf = 1e6;
vector<pair<int, int>> nxt[1000005];
vector<string> ans;
int drop[1000005];
bool chk(int i, int j)
{
    return 1 <= i && i <= N && 1 <= j && j <= M;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M; c.resize(N+1);
    for (int i = 1; i <= N; i++) {
        string s; cin >> s;
        s = " " + s; c[i] = s;
    }
    UnionFind uf(N*M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (c[i][j] == '#') {
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (chk(ni, nj) && c[ni][nj] == '#') {
                        uf.uni(num(i, j), num(ni, nj));
                    }
                }
            }
        }
    }
    for (int j = 1; j <= M; j++) {
        int prv = N + 1, cl = N*M;
        for (int i = N; i >= 1; i--) {
            if (c[i][j] == '.') continue;
            int x = uf.fin(num(i, j));
            nxt[cl].push_back(make_pair(x, prv - i - 1));
            cl = x, prv = i;
        }
    }
    fill(drop, drop + 1000005, inf);
    drop[N*M] = 0;
    priority_queue<pair<int, int>> pq; pq.push({0, N*M});
    while (!pq.empty()) {
        int cur = pq.top().second; pq.pop();
        for (pair<int, int> i:nxt[cur]) {
            if (drop[i.first] > drop[cur] + i.second) {
                drop[i.first] = drop[cur] + i.second;
                pq.push({-drop[i.first], i.first});
            }
        }
    }
    ans.resize(N+1);
    for (int i = 1; i <= N; i++) ans.resize(M+1);
    for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) ans[i][j] = '.';
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (c[i][j] == '#') ans[i+drop[uf.fin(num(i, j))]][j] = '#';
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout << ans[i][j];
        }
        cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27656 KB Output is correct
2 Correct 15 ms 27644 KB Output is correct
3 Correct 14 ms 27692 KB Output is correct
4 Correct 14 ms 27656 KB Output is correct
5 Correct 13 ms 27676 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 14 ms 27604 KB Output is correct
8 Correct 14 ms 27604 KB Output is correct
9 Correct 14 ms 27624 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Runtime error 42 ms 56024 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 70708 KB Output is correct
2 Correct 143 ms 75484 KB Output is correct
3 Correct 145 ms 77320 KB Output is correct
4 Correct 140 ms 70292 KB Output is correct
5 Correct 134 ms 81532 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27656 KB Output is correct
2 Correct 15 ms 27644 KB Output is correct
3 Correct 14 ms 27692 KB Output is correct
4 Correct 14 ms 27656 KB Output is correct
5 Correct 13 ms 27676 KB Output is correct
6 Correct 14 ms 27604 KB Output is correct
7 Correct 14 ms 27604 KB Output is correct
8 Correct 14 ms 27604 KB Output is correct
9 Correct 14 ms 27624 KB Output is correct
10 Correct 14 ms 27604 KB Output is correct
11 Runtime error 42 ms 56024 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -