Submission #410784

#	Time	Username	Problem	Language	Result	Execution time	Memory
410784		snasibov05	Clickbait (COCI18_clickbait)	C++14	12 / 120	38 ms	12476 KiB

clickbait

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define pb push_back

struct point{
    int x, y;
    point(){}
    point(int xx, int yy){
        x = xx;
        y = yy;
    }
};

struct container{
    int idx;
    point tl;
    point br;
    container(int i, int x1, int y1, int x2, int y2){
        idx = i;
        tl = point(x1, y1);
        br = point(x2, y2);
    }
};

bool isdigit(char c){
    return c >= '0' && c <= '9';
}

vector<vector<int>> ed;
vector<int> order;
vector<bool> visited;

void dfs(int cur){
    visited[cur] = true;
    for (auto x : ed[cur]){
        if (!visited[x]) dfs(x);
    }
    order.pb(cur);
}

int main() {
    int n, m; cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i){
        cin >> grid[i];
    }

    int v = 0;

    vector<container> a;
    vector<vector<int>> id(n, vector<int>(m, -1));

    // - Find containers
    // - Define them by indices, coordinates of top left and bottom right
    // - Define id's of borders of containers by the corresponding index
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            if (isdigit(grid[i][j])){
                int k = 0;
                while (isdigit(grid[i][j])) k = (k * 10) + grid[i][j++] - '0';
                j--;

                int x1 = i;
                while (grid[x1][j] != '-') x1--;
                int x2 = i;
                while (grid[x2][j] != '-') x2++;

                int y1 = j;
                while (grid[i][y1] != '|') y1--;
                int y2 = j;
                while (grid[i][y2] != '|') y2++;

                v = max(v, k);
                a.pb(container(k, x1, y1, x2, y2));

                for (int l = x1; l <= x2; ++l){
                    id[l][y1] = id[l][y2] = k;
                }

                for (int l = y1; l <= y2; ++l){
                    id[x1][l] = id[x2][l] = k;
                }
            }
        }
    }

    ed.resize(v+1);
    visited.resize(v+1);

    // - Follow the pathes coming from each container from bottom to top and add edges accordingly
    // - Directions ( 0 -> left, 1 -> right, 2 -> up, 3 -> down

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    for (container c : a){

        for (int j = c.br.x; j >= c.tl.x; --j){

            if (c.tl.y > 0 && grid[j][c.tl.y-1] == '-'){

                int dir = 2;
                point cur = point(j, c.tl.y);

                cur.x += dx[dir];
                cur.y += dy[dir];

                if (grid[cur.x][cur.y] == '+') dir = 1;

                while (id[cur.x][cur.y] == -1){
                    cur.x += dx[dir];
                    cur.y += dy[dir];

                    if (grid[cur.x][cur.y] == '+') dir = 1;
                }

                ed[c.idx].pb(id[cur.x][cur.y]);

            }

            if (c.br.y < m && grid[j][c.br.y+1] == '-') {
                int dir = 3;
                point cur = point(j, c.br.y);

                cur.x += dx[dir];
                cur.y += dy[dir];

                if (grid[cur.x][cur.y] == '+') dir = 1;

                while (id[cur.x][cur.y] == -1){
                    cur.x += dx[dir];
                    cur.y += dy[dir];

                    if (grid[cur.x][cur.y] == '+') dir = 1;
                }

                ed[c.idx].pb(id[cur.x][cur.y]);
            }

        }

    }

    dfs(1);

    for (auto x : order) cout << x << "\n";


    return 0;
}

• Subtask 1: 12 / 120