Submission #22401

#TimeUsernameProblemLanguageResultExecution timeMemory
22401카시코이 (#40)Young Zebra (KRIII5_YZ)C++14
0 / 7
66 ms14240 KiB
#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m; char board[403][403]; int visit[1203][1203]; int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 }; int out[403][403]; int outlist[1500000]; struct DJSet { vector<int> par, rank; int setCnt; DJSet(int _sz) : par(_sz), rank(_sz), setCnt(0) { init(); } void init() { setCnt = par.size(); for (int i = 0; i < par.size(); ++i) par[i] = i; fill(rank.begin(), rank.end(), 0); } int find(int p) { return p == par[p] ? p : (par[p] = find(par[p])); } bool merge(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (rank[a] > rank[b]) swap(a, b); par[a] = b; if (rank[a] == rank[b]) rank[b] += 1; --setCnt; return true; } }; int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%s", board[i]); } int cur = 0; for (int i = 0; i < 3 * n; ++i) { for (int j = 0; j < 3 * m; ++j) { if (visit[i][j]) continue; ++cur; int cnt = 0; bool ok = true; queue<pair<int, int>> q; visit[i][j] = cur; q.emplace(i, j); while (!q.empty()) { int ci = q.front().first, cj = q.front().second; q.pop(); ++cnt; for (int k = 0; k < 4; ++k) { int ni = ci + di[k], nj = cj + dj[k]; if (ni < 0 || ni >= n * 3 || nj < 0 || nj >= m * 3 || visit[ni][nj]) continue; if (board[ni % n][nj % m] != board[i % n][j % m]) continue; visit[ni][nj] = cur; q.emplace(ni, nj); } } outlist[cur] = cnt; } } DJSet dj(cur + 2); for (int i = 0; i < n * 3; ++i) { if (visit[i][0] == 0 || visit[i][m * 3 - 1] == 0) continue; if (board[i][0] == board[i][m - 1]) dj.merge(visit[i][0], visit[i][m * 3 - 1]); } for (int j = 0; j < m * 3; ++j) { if (visit[0][j] == 0 || visit[n * 3 - 1][j] == 0) continue; if (board[0][j] == board[n - 1][j]) dj.merge(visit[0][j], visit[n * 3 - 1][j]); } for (int i = n; i < n * 2; ++i) { for (int j = m; j < m * 2; ++j) { printf("%d ", outlist[visit[i][j]]); } putchar('\n'); } return 0; }

Compilation message (stderr)

YZ.cpp: In member function 'void DJSet::init()':
YZ.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < par.size(); ++i) par[i] = i;
                     ^
YZ.cpp: In function 'int main()':
YZ.cpp:55:9: warning: unused variable 'ok' [-Wunused-variable]
    bool ok = true;
         ^
YZ.cpp:42:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
YZ.cpp:44:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", board[i]);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...