Submission #246089

#	Time	Username	Problem	Language	Result	Execution time	Memory
246089		NONAME	Clickbait (COCI18_clickbait)	C++14	108 / 120	32 ms	13052 KiB

clickbait

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e3;

int n, m, mx, mk[N][N], mxx[N], mxy[N], mnx[N], mny[N];
bool used[N][N];
char c[N][N];
vector <int> order;

int f(int x, int y) {
    string s = "";
    while (y < m && (c[x][y] >= '0' && c[x][y] <= '9'))
        s += c[x][y++];

    return atoi(s.c_str());
}

void fill_all(int num, int sx, int sy) {
    queue <pair <int, int> > q;

    q.push(make_pair(sx, sy));
    used[sx][sy] = 1;

    mxx[num] = mxy[num] = 0;
    mnx[num] = mny[num] = N;

    while (!q.empty()) {
        auto p = q.front();
        q.pop();

        mk[p.first][p.second] = num;
        mxx[num] = max(mxx[num], p.first);
        mnx[num] = min(mnx[num], p.first);
        mxy[num] = max(mxy[num], p.second);
        mny[num] = min(mny[num], p.second);

        if (c[p.first][p.second] == '-' || c[p.first][p.second] == '|')
            continue;

        int steps[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

        for (int i = 0; i < 4; ++i) {
            int cx = p.first + steps[i][0];
            int cy = p.second + steps[i][1];

            if (cx >= 0 && cx < n && cy >= 0 && cy < m && !used[cx][cy]) {
                used[cx][cy] = 1;
                q.push(make_pair(cx, cy));
            }
        }
    }
}

int nxt(int x, int y) {
    int num = 0;
    queue <pair <int, int> > q;
    q.push(make_pair(x, y));

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        if (mk[x][y] != -1) {
            num = mk[x][y];
            break;
        }

        if (c[x][y] == '-') {
            if (y + 1 < m && (c[x][y + 1] == '-' || c[x][y + 1] == '+') && !used[x][y + 1]) {
                used[x][y + 1] = 1;
                q.push(make_pair(x, y + 1));
            }

            if (y - 1 >= 0 && (c[x][y - 1] == '-' || c[x][y - 1] == '+') && !used[x][y - 1]) {
                used[x][y - 1] = 1;
                q.push(make_pair(x, y - 1));
            }
        }

        if (c[x][y] == '|') {
            used[x + 1][y] = 1;
            q.push(make_pair(x + 1, y));
        }

        if (c[x][y] == '+') {
            if (x + 1 < n && c[x + 1][y] != '.' && !used[x + 1][y]) {
                used[x + 1][y] = 1;
                q.push(make_pair(x + 1, y));
            }

            if (x - 1 >= 0 && c[x - 1][y] != '.' && !used[x - 1][y]) {
                used[x - 1][y] = 1;
                q.push(make_pair(x - 1, y));
            }

            if (y + 1 < m && c[x][y + 1] != '.' && !used[x][y + 1]) {
                used[x][y + 1] = 1;
                q.push(make_pair(x, y + 1));
            }

            if (y - 1 >= 0 && c[x][y - 1] != '.' && !used[x][y - 1]) {
                used[x][y - 1] = 1;
                q.push(make_pair(x, y - 1));
            }
        }
    }

    return num;
}

void dfs(int v) {
    --mxx[v];
    while (mxx[v] > mnx[v]) {
        if (mny[v] - 1 >= 0 && c[mxx[v]][mny[v] - 1] == '-')
            dfs(nxt(mxx[v], mny[v] - 1));

        if (mxy[v] + 1 < m && c[mxx[v]][mxy[v] + 1] == '-')
            dfs(nxt(mxx[v], mxy[v] + 1));

        --mxx[v];
    }

    order.push_back(v);
}

int main() {
    fast_io;

    cin >> n >> m;

    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        cin >> c[i][j], mk[i][j] = -1;

    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
        if (used[i][j])
            continue;

        if (!(c[i][j] >= '0' && c[i][j] <= '9'))
            continue;

        int num = f(i, j);
        mx = max(mx, num);

        fill_all(num, i, j);
    }

    dfs(1);

    for (int i : order)
        cout << i << "\n";
}

• Subtask 1: 108 / 120