Submission #58258

ソースコード

?
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
136
137
138
139
140
141
142
143
144
145
146
// "header" {{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>
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 int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr long long mod1 = 1000000007;
constexpr long long mod2 = 998244353;
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
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); }
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;
inline int64_t updiv(int64_t n,int64_t d){ return ((n + d -1) / d); }
inline int square(int a){ return a * a; }
// }}}
//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;
}
};
//}}}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
int h,w,q;
cin >> h >> w >> q;
UnionFind uf(h*w+1);
vector<vector<int> > num(h,vector<int>(w));
vector<string> mat(h);
int cnt = 0;
rep(i,h){
cin >> mat[i];
rep(j,w){
num[i][j] = cnt;
++cnt;
}
}
auto inside = [&](int y,int x){
return (y < h && x < w && y >= 0 && x >= 0);
};
vector<vector<bool> > visited(h,vector<bool>(w));
rep(i,h){
rep(j,w){
if(visited[i][j] || mat[i][j] == '.') continue;
queue<pii> que;
que.emplace(i,j);
while(!que.empty()){
int y,x;
tie(y,x) = que.front();
que.pop();
rep(k,4){
int ny = y + dy[k];
int nx = x + dx[k];
if(inside(ny,nx) && mat[ny][nx] == '#' && !visited[ny][nx]){
visited[ny][nx] = true;
que.emplace(ny,nx);
uf.unite(num[y][x],num[ny][nx]);
}
}
}
}
}
rep(i,q){
int com,y,x;
cin >> com >> y >> x;
--y,--x;
if(com){
cout << (mat[y][x] == '#' ? uf.size(num[y][x]) : 0) << '\n';
}else{
rep(j,4){
int ny = y + dy[j];
int nx = x + dx[j];
if(inside(ny,nx) && mat[ny][nx] == '#'){
uf.unite(num[y][x],num[ny][nx]);
}
}
mat[y][x] = '#';
}
}
return 0;
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 ei1903
投稿日時 2020-01-24 17:50:11
言語 C++14
状態 Accepted
得点 10
ソースコード長 3795 Byte
最大実行時間 337 ms
最大メモリ使用量 36496 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 30 ms 604 KB
1
2
input-sample2 AC 24 ms 684 KB
1
2
input01-easy AC 18 ms 1020 KB
1
2
input02-easy AC 29 ms 904 KB
1
2
input03-easy AC 21 ms 1248 KB
1
2
input04 AC 218 ms 23376 KB
2
input05 AC 151 ms 22540 KB
2
input06 AC 209 ms 21528 KB
2
input07 AC 203 ms 22448 KB
2
input08 AC 201 ms 30036 KB
2
input09 AC 232 ms 31360 KB
2
input10 AC 337 ms 32052 KB
2
input11 AC 242 ms 35948 KB
2
input12 AC 167 ms 36496 KB
2
input13 AC 19 ms 11852 KB
2
input14 AC 23 ms 11936 KB
2