Submission #58529

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
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); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x) setprecision(x)
struct Unionfind{
vector<int> rank,p,si;//木の高さの管理=rank,p=親の管理
Unionfind(){}
//初期化
Unionfind(int size){
rank.resize(size,0);
p.resize(size,0);
si.resize(size,1);
for(int i=0;i<size;i++){
makeSet(i);
}
}
void makeSet(int x){
p[x]=x;//親を自分にする。
rank[x]=0;//最初の高さは0
si[x]=1;
}
//同じ集合か判定。
bool same(int x,int y){
return (findSet(x)==findSet(y));
}
//集合を併合
void unite(int x,int y){
link(findSet(x),findSet(y));
}
void link(int x,int y){
if(x!=y){
if(rank[x]<rank[y]){
p[x]=y;
si[y]+=si[x];
}
else{
p[y]=x;
if(rank[x]==rank[y]){
rank[y]++;
}
si[x]+=si[y];
}
}//cout<<rank[x]<<' '<<rank[y]<<'\n';
}
int siz(int x){
int a=findSet(x);
return si[a];
}
//経路圧縮
int findSet(int x){
//自分自身と親が等しくなるまで再帰
if(x!=p[x]){
p[x]=findSet(p[x]);
}
return p[x];
}
};
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
int h,w,q;
cin>>h>>w>>q;
vector<string> s(h);
rep(i,h){
cin>>s[i];
}
vector<vector<pair<int,bool> > >flag(h+2,vector<pair<int,bool> >(w+2));
int count=1;
rep(i,h+2){
rep(j,w+2){
flag[i][j].second=false;
}
}
REP(i,1,h+1){
REP(j,1,w+1){
flag[i][j].first=count;
count++;
}
}
rep(i,h){
rep(j,w){
if(s[i][j]=='#'){
flag[i+1][j+1].second=true;
}
}
}
Unionfind uf((h+2)*(w+2));
REP(i,1,h+1){
REP(j,1,w+1){
if(flag[i][j].second){
rep(k,4){
if(flag[i+dx[k]][j+dy[k]].second){
uf.unite(flag[i][j].first,flag[i+dx[k]][j+dy[k]].first);
}
}
}
}
}
int que,x,y;
rep(i,q){
cin>>que>>x>>y;
if(que==1){
if(flag[x][y].second){
cout<<uf.siz(flag[x][y].first)<<'\n';
}
else{
cout<<0<<'\n';
}
}
else{
flag[x][y].second=true;
rep(j,4){
if(flag[x+dx[j]][y+dy[j]].second){
uf.unite(flag[x][y].first,flag[x+dx[j]][y+dy[j]].first);
}
}
}
}
/* rep(i,h+1){
rep(j,w+1){
cout<<uf.siz(flag[i][j].first)<<' ';
}
cout<<'\n';
}*/
return(0);
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 ei1918
投稿日時 2020-02-07 16:24:29
言語 C++14
状態 Accepted
得点 10
ソースコード長 3355 Byte
最大実行時間 295 ms
最大メモリ使用量 32540 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 22 ms 604 KB
1
2
input-sample2 AC 25 ms 680 KB
1
2
input01-easy AC 17 ms 884 KB
1
2
input02-easy AC 19 ms 944 KB
1
2
input03-easy AC 27 ms 1216 KB
1
2
input04 AC 226 ms 19744 KB
2
input05 AC 146 ms 19108 KB
2
input06 AC 202 ms 18464 KB
2
input07 AC 255 ms 19448 KB
2
input08 AC 244 ms 25924 KB
2
input09 AC 268 ms 27288 KB
2
input10 AC 295 ms 28144 KB
2
input11 AC 201 ms 32072 KB
2
input12 AC 190 ms 32540 KB
2
input13 AC 28 ms 11764 KB
2
input14 AC 24 ms 11848 KB
2