Submission #58528

ソースコード

?
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
最大実行時間 267 ms
最大メモリ使用量 32512 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 21 ms 604 KB
1
2
input-sample2 AC 16 ms 424 KB
1
2
input01-easy AC 22 ms 752 KB
1
2
input02-easy AC 27 ms 812 KB
1
2
input03-easy AC 23 ms 1204 KB
1
2
input04 AC 235 ms 19728 KB
2
input05 AC 167 ms 19096 KB
2
input06 AC 240 ms 18452 KB
2
input07 AC 267 ms 19564 KB
2
input08 AC 229 ms 25912 KB
2
input09 AC 262 ms 27404 KB
2
input10 AC 249 ms 28128 KB
2
input11 AC 179 ms 32052 KB
2
input12 AC 189 ms 32512 KB
2
input13 AC 27 ms 11732 KB
2
input14 AC 19 ms 11692 KB
2