Submission #58527

ソースコード

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 39 ms 476 KB
1
2
input-sample2 AC 24 ms 556 KB
1
2
input01-easy AC 20 ms 756 KB
1
2
input02-easy AC 21 ms 812 KB
1
2
input03-easy AC 21 ms 1212 KB
1
2
input04 AC 255 ms 19864 KB
2
input05 AC 189 ms 19232 KB
2
input06 AC 238 ms 18456 KB
2
input07 AC 280 ms 19312 KB
2
input08 AC 186 ms 25916 KB
2
input09 AC 250 ms 27408 KB
2
input10 AC 275 ms 28008 KB
2
input11 AC 186 ms 31928 KB
2
input12 AC 191 ms 32528 KB
2
input13 AC 20 ms 11872 KB
2
input14 AC 22 ms 11828 KB
2