結果
問題 | No.697 池の数はいくつか |
ユーザー | ramia777 |
提出日時 | 2022-06-01 17:05:12 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,147 ms / 6,000 ms |
コード長 | 3,888 bytes |
コンパイル時間 | 1,255 ms |
コンパイル使用メモリ | 98,708 KB |
実行使用メモリ | 144,676 KB |
最終ジャッジ日時 | 2024-04-25 21:09:31 |
合計ジャッジ時間 | 10,133 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
9,820 KB |
testcase_01 | AC | 3 ms
9,816 KB |
testcase_02 | AC | 2 ms
9,816 KB |
testcase_03 | AC | 3 ms
10,068 KB |
testcase_04 | AC | 3 ms
9,820 KB |
testcase_05 | AC | 3 ms
9,940 KB |
testcase_06 | AC | 3 ms
9,960 KB |
testcase_07 | AC | 2 ms
9,824 KB |
testcase_08 | AC | 3 ms
9,936 KB |
testcase_09 | AC | 2 ms
9,932 KB |
testcase_10 | AC | 2 ms
9,956 KB |
testcase_11 | AC | 3 ms
9,824 KB |
testcase_12 | AC | 3 ms
9,940 KB |
testcase_13 | AC | 2 ms
9,964 KB |
testcase_14 | AC | 3 ms
9,952 KB |
testcase_15 | AC | 2 ms
9,944 KB |
testcase_16 | AC | 3 ms
9,928 KB |
testcase_17 | AC | 3 ms
9,952 KB |
testcase_18 | AC | 3 ms
10,068 KB |
testcase_19 | AC | 2 ms
9,936 KB |
testcase_20 | AC | 3 ms
9,964 KB |
testcase_21 | AC | 2 ms
9,824 KB |
testcase_22 | AC | 2 ms
9,816 KB |
testcase_23 | AC | 2 ms
9,964 KB |
testcase_24 | AC | 123 ms
32,700 KB |
testcase_25 | AC | 119 ms
32,584 KB |
testcase_26 | AC | 118 ms
32,164 KB |
testcase_27 | AC | 117 ms
32,120 KB |
testcase_28 | AC | 125 ms
34,216 KB |
testcase_29 | AC | 970 ms
109,952 KB |
testcase_30 | AC | 1,083 ms
144,676 KB |
testcase_31 | AC | 941 ms
109,944 KB |
testcase_32 | AC | 1,060 ms
144,632 KB |
testcase_33 | AC | 1,062 ms
144,508 KB |
testcase_34 | AC | 1,147 ms
144,556 KB |
ソースコード
// yukicodr // No.697 //二次元可変配列 //vector <vector <int>> mass; //vector <vector <int>> memo; //vector <int> memo; //#include "stdafx.h" #include <iostream> #include <vector> #include <list>//list #include <queue> //queue #include <set> //tree #include <map> //連想配列 #include <unordered_set> //hash #include <unordered_map> //hash #include <algorithm> #include <iomanip> #include <cstring> //#include <bits/stdc++.h> using namespace std; #define FOR(x,to) for(x=0;x<to;x++) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define FMAX(a,b) ((a)>(b)?(a):(b)) #define FMIN(a,b) ((a)<(b)?(a):(b)) #define FCEIL(a,b) ((a)+(b)-1)/(b) typedef unsigned long long ULL; typedef signed long long SLL; queue<int> _queue; //昇順 int compare_up(const int * a, const int *b) { if (*a > *b) return (1); else if (*a < *b) return (-1); return (0); } //降順 int compare_down(const int * a, const int *b) { if (*a > *b) return (-1); else if (*a < *b) return (1); return (0); } int par[3005*3005]; //ルートの番号 int _rank[3005*3005]; //木の高さ int flag[3005 * 3005]; // 経路圧縮 // 直列で連結しているような木はすべて直接ルートにつなぐようにする int _find(int x) { if (x == par[x]) { //cout << "x=" << x << endl; return x; } else { int a; //cout << "in->" << endl; a = _find(par[x]); //cout << "<-out" << endl; //cout << "x=" << x << ",par[x]=" << par[x] << ",a=" << a << endl; //ルートを更新(圧縮) par[x] = a; //新しいルートを返す return par[x]; } } //xとyが同じ集合かどうか bool same(int x, int y) { //ルートが同じかどうかを判定すればOK return _find(x) == _find(y); } //初期化 //はじめは全部の頂点がルート void init (int n) { for (int i = 0; i < n; i++) { par[i] = i; _rank[i] = 0; } } // x と y を同じツリーにする void _union(int x, int y) { int root_x; int root_y; root_x = _find(x); root_y = _find(y); if (root_x == root_y) return; //最初から同じルートならすぐ返す //木の高さが高いほうの木の根に、低いほうの根をつなげる if (_rank[root_x] < _rank[root_y]) { // x<yのとき par[root_x] = root_y; } else { // x>y または x==y のとき // yをxにつなげる par[root_y] = root_x; // 高さが同じときだけ 高さを変える必要がある if (_rank[root_x] == _rank[root_y]) _rank[root_x]++; // つなげられた木の高さを1つふやす(全体の木の高さは1増える) } } int W, H; int A[3005][3005]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,-1,0,1}; int main() { cin >> H; cin >> W; for (int y = 0; y < H; y++) for (int x = 0; x < W; x++) { scanf("%d", &A[y][x]); } init(H*W); for (int y = 0; y < H; y++) { for (int x = 0; x < W; x++) { //池のとき if (A[y][x]) { for (int k = 0; k < 4; k++) { int nx, ny; nx = x + dx[k]; ny = y + dy[k]; if (nx >= 0 && nx < W && ny >= 0 && ny < H) { //現在値の前後左右で池(1)があれば同じグループにする if (A[ny][nx]) { //同じ池グループかどうか確認 if (false == same(y*W + x, ny*W + nx)) { //同じグループでなければ同じグループにする _union(y*W + x, ny*W + nx); } } } } } } } int ans = 0; for (int y = 0; y < H; y++) { for (int x = 0; x < W; x++) { if (A[y][x]) { par[y*W + x] = _find(par[y*W + x]); if (!flag[par[y*W + x]]) { ans++; flag[par[y*W + x]] = 1; } //printf("%3d,", par[y*W + x]); } //else //printf(" * ,"); } //cout << endl; } cout << ans << endl; //getchar(); return 0; }