Submission #239787

#	Time	Username	Problem	Language	Result	Execution time	Memory
239787		VEGAnn	Clickbait (COCI18_clickbait)	C++14	108 / 120	58 ms	62072 KiB

clickbait

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PB push_back
#define sz(x) ((int)x.size())
#define i3 array<int,3>
#define i2 array<int,2>
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
const int N = 1010;
const int M = 510;
const int K = 110;
const int T = 2010;
const int oo = 2e9;
const int MX = 1000100;
vector<int> ts;
string mem[MX], nw;
vector<i2> g[MX];
char c[N][N];
int n, m, cnt = 0, mrk[N][N];
bool used[N][N], ok[N][N];

void filll(int x, int y, int cl){
    if (mrk[x][y] > 0) return;

    mrk[x][y] = cl;

    if (c[x][y] == '-' || c[x][y] == '|') return;

    if (x > 0) filll(x - 1, y, cl);
    if (x < n - 1) filll(x + 1, y, cl);
    if (y < m - 1) filll(x, y + 1, cl);
    if (y > 0) filll(x, y - 1, cl);
}

void dfs(int v){
    if (sz(g[v]) > 0){
        sort(all(g[v]));
        reverse(all(g[v]));

        for (i2 u : g[v])
            dfs(u[1]);
    }

    ts.PB(v);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        cin >> c[i][j];
        ok[i][j] = bool(c[i][j] == '|' || c[i][j] == '+' || c[i][j] == '-');
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (c[i][j] >= '1' && c[i][j] <= '9' && mrk[i][j] == 0){
            nw = c[i][j];

            int jj = j + 1;

            while (jj < m && c[i][jj] >= '0' && c[i][jj] <= '9'){
                nw += c[i][jj];
                jj++;
            }

            mem[++cnt] = nw;

            filll(i, j, cnt);

            if (mem[cnt] == "1") continue;

            int ii = i, mj = -1;

            jj = j;

            while (c[ii][jj] != '-')
                ii--;

            while (c[ii][jj] != '+'){
                if (c[ii - 1][jj] == '|')
                    mj = jj;

                jj--;
            }

            jj = j;

            while (c[ii][jj] != '+'){
                if (c[ii - 1][jj] == '|')
                    mj = jj;

                jj++;
            }

            jj = mj;

            used[ii][jj] = 1;

            ii--;

            while (1){
                used[ii][jj] = 1;

                if (c[ii][jj] == '|')
                    ii--;
                else if (c[ii][jj] == '+'){
                    if (jj > 0 && !used[ii][jj - 1] && ok[ii][jj - 1])
                        jj--;
                    else if (jj + 1 < m && !used[ii][jj + 1] && ok[ii][jj + 1])
                        jj++;
                    else ii--;
                } else {
                    if (jj > 0 && !used[ii][jj - 1] && ok[ii][jj - 1])
                        jj--;
                    else jj++;

                    if (mrk[ii][jj] > 0){
                        g[mrk[ii][jj]].PB({ii, cnt});
                        break;
                    }
                }
            }
        }

    dfs(1);

    for (int cr : ts)
        cout << mem[cr] << '\n';

    return 0;
}

• Subtask 1: 108 / 120