Submission #56355

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// "header" {{{
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <tuple>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define int long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
inline double sqrt( const double &x)
{
double xHalf = 0.5 * x;
int64_t tmp = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
double xRes = * (double*)&tmp;
xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
return xRes * x;
}
// }}}
//UnionFind{{{
struct UnionFind {
vector < int > par;
vector < int > siz;
UnionFind(int n): par(n), siz(n, 1) { //初期化
for(int i = 0; i < n; i++) par[i] = i;
}
int root(int x){ //根の更新＋判定
if(par[x] == x) return x;
else return par[x] = root(par[x]);
}
int size(int x){ //サイズ
return siz[root(x)];
}
bool same(int x, int y){ //グループの判定
return root(x) == root(y);
}
bool unite(int x, int y){ //つなげる
if((x=root(x))==(y=root(y))) return false;
if( siz[y] > siz[x] ) swap(x,y);
siz[x] += siz[y];
par[y] = x;
return true;
}
};
//}}}
int h,w,q;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
bool inside(int y,int x){
return (y < h && x < w && y >= 0 && x >= 0);
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> h >> w >> q;
UnionFind uf(h * w);
vector<string> mas(h);
vector<vector<int> > number(h,vector<int>(w));
int cnt = 0;
rep(i,h){
cin >> mas[i];
rep(j,w){
number[i][j] = cnt;
++cnt;
}
}
rep(i,h){
rep(j,w){
if(mas[i][j] == '#'){
rep(k,4){
int ny = i + dy[k];
int nx = j + dx[k];
if(inside(ny,nx) && mas[ny][nx] == '#'){
uf.unite(number[i][j],number[ny][nx]);
}
}
}
}
}
rep(loop,q){
int com,y,x;
cin >> com >> y >> x;
--y;
--x;
if(com){
cout << (mas[y][x] == '#' ? uf.size(number[y][x]) : 0) << '\n';
}
else{
mas[y][x] = '#';
rep(i,4){
int ny = y + dy[i];
int nx = x + dx[i];
if(inside(ny,nx) && mas[ny][nx] == '#'){
uf.unite(number[y][x],number[ny][nx]);
}
}
}
}
return 0;
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 ei1903
投稿日時 2019-11-13 16:47:04
言語 C++14
状態 Accepted
得点 10
ソースコード長 3035 Byte
最大実行時間 337 ms
最大メモリ使用量 82760 KB

セット

セット 得点 Cases
1 Easy 1 / 1 *easy, *sample*
2 ALL 9 / 9 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 44 ms 604 KB
1
2
input-sample2 AC 39 ms 688 KB
1
2
input01-easy AC 28 ms 892 KB
1
2
input02-easy AC 36 ms 1036 KB
1
2
input03-easy AC 21 ms 1396 KB
1
2
input04 AC 261 ms 28140 KB
2
input05 AC 153 ms 30656 KB
2
input06 AC 201 ms 34144 KB
2
input07 AC 236 ms 39944 KB
2
input08 AC 208 ms 53168 KB
2
input09 AC 231 ms 60436 KB
2
input10 AC 337 ms 66808 KB
2
input11 AC 211 ms 76384 KB
2
input12 AC 222 ms 82760 KB
2
input13 AC 29 ms 58288 KB
2
input14 AC 30 ms 58240 KB
2