Submission #40900

ソースコード

?
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
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <functional>
using namespace std;
#define elif else if
#define echo cout <<
#define read cin >>
#define fin << '\n'
#define finn cout << '\n'
typedef long long llong;
typedef bool boolean;
typedef pair<int,int> pii;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
boolean canMove(int x,int y,int w,int h){return (x>=0&&y>=0&&x<w&&y<h);};
const int INF = 1 << 29;
char mas[1010][1919];
int id[1010][1010];
int size[100100100];
bool hunt[1010][1010];
int h, w;
int parent[100100100];
int __rank[100100100];
int find( int i ) {
if ( i != parent[i] ) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite ( int x, int y ) {
int xRoot = find(x);
int yRoot = find(y);
if ( __rank[xRoot] > __rank[yRoot] ) {
parent[yRoot] = xRoot;
}
elif ( __rank[xRoot] < __rank[yRoot] ) {
parent[xRoot] = yRoot;
}
else {
parent[yRoot] = xRoot;
__rank[xRoot]++;
}
}
boolean isSame( int x, int y ) {
return ( find(x) == find(y) );
}
void bfs( int sx, int sy ) {
int counter = 1;
queue<pii> que;
que.push( make_pair( sy, sx ) );
hunt[sy][sx] = true;
while ( !que.empty() ) {
pii now = que.front();
que.pop();
int y = now.first;
int x = now.second;
for ( int i = 0; i < 4; i++ ) {
int nx = x + dx[i];
int ny = y + dy[i];
if ( canMove(nx, ny, w, h) && mas[ny][nx] == '#' && !hunt[ny][nx] ) {
hunt[ny][nx] = true;
unite ( id[sy][sx], id[ny][nx] );
que.push( make_pair ( ny, nx ) );
counter++;
}
}
}
int root = find(id[sy][sx]);
size[root] = counter;
}
signed main(){
cin.tie(0); ios::sync_with_stdio(false);
for ( int i = 0; i < 10001000; i++ ) {
parent[i] = i;
}
int q;
memset ( hunt, 0, sizeof( hunt ) );
read h >> w >> q;
for ( int i = 0; i < h; i++ ) {
read mas[i];
}
for ( int i = 0; i < h; i++ ) {
for ( int j = 0; j < w; j++ ) {
id[i][j] = ( 1000 * i ) + j;
}
}
for ( int i = 0; i < h; i++ ) {
for ( int j = 0; j < w; j++ ) {
if ( !hunt[i][j] && mas[i][j] == '#' ) {
bfs(j, i);
}
}
}
for ( int i = 0; i < q; i++ ) {
int com, x, y;
read com >> y >> x;
x--; y--;
if ( com == 0 ) {
mas[y][x] = '#';
int newSize = 1;
for ( int j = 0; j < 4; j++ ) {
int nx = x + dx[j];
int ny = y + dy[j];
if ( canMove(nx, ny, w, h) && !isSame(id[y][x], id[ny][nx]) && mas[ny][nx] == '#') {
int root = find(id[ny][nx]);
newSize += size[root];
unite( id[y][x], id[ny][nx] );
}
}
int root = find(id[y][x]);
size[root] = newSize;
}
else {
if ( mas[y][x] == '.' ) {
echo 0 fin;
}
else {
int root = find(id[y][x]);
echo size[root] fin;
}
}
}
return 0;
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 r1825
投稿日時 2018-08-09 09:22:51
言語 C++14
状態 Accepted
得点 10
ソースコード長 3589 Byte
最大実行時間 281 ms
最大メモリ使用量 73484 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 38 ms 51680 KB
1
2
input-sample2 AC 31 ms 51648 KB
1
2
input01-easy AC 33 ms 51984 KB
1
2
input02-easy AC 29 ms 52260 KB
1
2
input03-easy AC 34 ms 52356 KB
1
2
input04 AC 214 ms 63108 KB
2
input05 AC 147 ms 61352 KB
2
input06 AC 198 ms 64516 KB
2
input07 AC 202 ms 63256 KB
2
input08 AC 203 ms 66924 KB
2
input09 AC 214 ms 62140 KB
2
input10 AC 281 ms 68988 KB
2
input11 AC 197 ms 66768 KB
2
input12 AC 181 ms 73484 KB
2
input13 AC 30 ms 62944 KB
2
input14 AC 31 ms 62900 KB
2