結果
問題 | No.697 池の数はいくつか |
ユーザー | T101010101 |
提出日時 | 2023-01-06 11:44:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 6,152 bytes |
コンパイル時間 | 3,503 ms |
コンパイル使用メモリ | 268,304 KB |
実行使用メモリ | 695,776 KB |
最終ジャッジ日時 | 2023-08-20 06:13:05 |
合計ジャッジ時間 | 17,261 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 1 ms
4,384 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,384 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 2 ms
4,380 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 1 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 194 ms
79,888 KB |
testcase_25 | AC | 199 ms
80,200 KB |
testcase_26 | AC | 189 ms
80,288 KB |
testcase_27 | AC | 201 ms
80,028 KB |
testcase_28 | AC | 201 ms
79,888 KB |
testcase_29 | MLE | - |
testcase_30 | MLE | - |
testcase_31 | MLE | - |
testcase_32 | MLE | - |
testcase_33 | MLE | - |
testcase_34 | MLE | - |
ソースコード
#pragma region Macros #include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; // using namespace __gnu_cxx; // #include <boost/multiprecision/cpp_int.hpp> // namespace mp = boost::multiprecision; // using Bint = mp::cpp_int; #define TO_STRING(var) # var #define pb emplace_back #define int ll #define endl '\n' using ll = long long; using ld = long double; const ld PI = acos(-1); const ld EPS = 1e-10; const int INF = 1 << 30; const ll INFL = 1LL << 61; // const int MOD = 998244353; const int MOD = 1000000007; __attribute__((constructor)) void constructor() { ios::sync_with_stdio(false); cin.tie(nullptr); // ifstream in("input.txt"); // cin.rdbuf(in.rdbuf()); cout << fixed << setprecision(15); } template<int mod> class modint{ public: int val = 0; modint(int x = 0) { while (x < 0) x += mod; val = x % mod; } modint(const modint &r) { val = r.val; } modint operator -() { return modint(-val); } modint operator +(const modint &r) { return modint(*this) += r; } modint operator -(const modint &r) { return modint(*this) -= r; } modint operator *(const modint &r) { return modint(*this) *= r; } modint operator /(const modint &r) { return modint(*this) /= r; } modint &operator +=(const modint &r) { val += r.val; if (val >= mod) val -= mod; return *this; } modint &operator -=(const modint &r) { if (val < r.val) val += mod; val -= r.val; return *this; } modint &operator *=(const modint &r) { val = val * r.val % mod; return *this; } modint &operator /=(const modint &r) { int a = r.val, b = mod, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % mod; if (val < 0) val += mod; return *this; } bool operator ==(const modint& r) { return this -> val == r.val; } bool operator <(const modint& r) { return this -> val < r.val; } bool operator !=(const modint& r) { return this -> val != r.val; } }; using mint = modint<MOD>; istream &operator >>(istream &is, mint& x) { int t; is >> t; x = t; return (is); } ostream &operator <<(ostream &os, const mint& x) { return os << x.val; } mint modpow(const mint &a, int n) { if (n == 0) return 1; mint t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } int modpow(int x, int n, int mod) { int ret = 1; while (n > 0) { if (n % 2 == 1) ret = ret * x % mod; x = x * x % mod; n /= 2; } return ret; } int ceil(int x, int y) { return (x > 0 ? (x + y - 1) / y : x / y); } #pragma endregion class UnionFind { public: UnionFind() = default; UnionFind(int n) : par(n), // max_node(n), TODO // min_node(n), TODO sz(n, 1) { iota(par.begin(), par.end(), 0); } // https://algo-method.com/tasks/561 // UnionFind(int n, const vector<int>& V) : par(n), sum(V), // sz(n, 1) { iota(par.begin(), par.end(), 0); } int root(int x) { if (par[x] == x) return x; return (par[x] = root(par[x])); } bool unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return false; // union by size (小さいほうが子になる) if (sz[rx] < sz[ry]) swap(rx, ry); sz[rx] += sz[ry]; par[ry] = rx; // sum[rx] += sum[ry]; // max_node[rx] = max(max_node[rx], max_node[ry]); // min_node[rx] = min(min_node[rx], min_node[ry]); return true; } bool issame(int x, int y) { return (root(x) == root(y)); } // xが属するグループの要素数を返す int size(int x) { return sz[root(x)]; } // xが属するグループの{重さ}の合計値 int get_sum(int x) { return sum[root(x)]; } // xを含む根付き木の中での頂点番号の最大値 // int get_max(int x) { // return max_node[root(x)]; // } // xを含む根付き木の中での頂点番号の最小値 // int get_min(int x) { // return min_node[root(x)]; // } // 各素集合ごとに分割。G[i](0 <= i < K)の隣接リスト vector<vector<int>> groups(int n) { vector<vector<int>> G(n); for (int x = 0; x < n; x++) { G[root(x)].push_back(x); } G.erase( remove_if(G.begin(), G.end(), [&](const vector<int>& v) { return v.empty(); }), G.end()); return G; } private: // rootの場合は自身が親 vector<int> par; // グループの要素数(root用) // xがroot のときのみ, sz[x] はそのグループに属する要素数を表す vector<int> sz; // 渡された配列の合計値 vector<int> sum; // 集合内の最大の頂点番号と最小の頂点番号 vector<int> max_node; vector<int> min_node; }; const vector<int> dx = {1, 0, -1, 0}; const vector<int> dy = {0, -1, 0, 1}; int H, W; bool isvalid(int x, int y) { if (x >= 0 && x < H && y >= 0 && y < W) return true; else return false; } int getnum(int x, int y) { return (x * W + y); } signed main() { cin >> H >> W; vector<vector<int>> A(H, vector<int>(W)); vector<int> B(H * W); // Aを一次元化 UnionFind uf(H * W); // UFでグラフを構築 for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cin >> A[i][j]; if (A[i][j] == 1) { for (int k = 0; k < 4; k++) { B[getnum(i, j)] = true; int x = i + dx[k]; int y = j + dy[k]; if (!isvalid(x, y)) continue; if (A[x][y] == 1) { uf.unite(getnum(i, j), getnum(x, y)); } } } } } vector<vector<int>> G = uf.groups(H * W); // 連結成分ごとに分解(0は孤立グループ) int ans = G.size(); for (int i = 0; i < (int)G.size(); i++) { if (B[G[i][0]] == 0) ans--; } cout << ans << endl; }