Submission #704465

#	Time	Username	Problem	Language	Result	Execution time	Memory
704465		BrineTw	Dijamant (COCI22_dijamant)	C++14	0 / 70	1 ms	436 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> temp(h);
    for (auto& s: temp) cin >> s;
    vector< vector<int> > graph(h + 2, vector<int>(w + 2, -1));
    vector< vector<int> > visited(h + 2, vector<int>(w + 2, 0));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (temp[i][j] == '#') {
                graph[i + 1][j + 1] = 1;
            } else {
                graph[i + 1][j + 1] = 0;
            }
        }
    }
    
    set< pair<int, int> > s;
    int white = 0, black;
    for (int i = 1; i <= 1000; i++) {
        s.insert({white, 4 * i});
        white += 4 * i;
    }

    int ans = 0;
    int tried = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (visited[i][j]) continue;

            white = black = 0;

            queue<pair<int, int> > q;
            q.push({i, j});
            visited[i][j] = ++tried;

            int ny, nx;
            bool flag = 1;
            while (q.size()) {
                auto& [y, x] = q.front();

                for (int i = 0; i < 4; i++) {
                    ny = y + dy[i];
                    nx = x + dx[i];

                    if (visited[ny][nx] >= tried) continue;
                    visited[ny][nx] = tried;

                    if (graph[ny][nx] < 0) {
                        flag = 0;
                    } else {
                        if (graph[ny][nx] == 1) black++;
                        if (graph[ny][nx] == 0) {
                            white++;
                            q.push({ny, nx});
                        }
                    }
                }
                // cerr << q.size() << '\n';
                q.pop();
            }

            
            // cerr << white << ' ' << black << '\n';
            // cerr << i << ", " << j << '\n';
            if (flag && s.find({white, black}) != s.end()) {
                // cerr << "-----\n";
                ans++;
            }
        }
    }

    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |                 auto& [y, x] = q.front();
      |                       ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 50