Submission #58500

ソースコード

?
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
#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;//木の高さの管理=rank,p=親の管理
Unionfind(){}
//初期化
Unionfind(int size){
rank.resize(size,1);
p.resize(size,0);
for(int i=0;i<size;i++){
makeSet(i);
}
}
void makeSet(int x){
p[x]=x;//親を自分にする。
rank[x]=1;//最初の高さは0
}
//同じ集合か判定。
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){
rank[x]+=rank[y];
}
p[y]=x;
//cout<<rank[x]<<' '<<rank[y]<<'\n';
}
int ranksum(int x){
int a,b;
a=findSet(x);
return rank[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.ranksum(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);
}
}
}
}
return(0);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 28 ms 600 KB
1
2
input-sample2 AC 20 ms 552 KB
1
2
input01-easy AC 24 ms 888 KB
1
2
input02-easy AC 25 ms 868 KB
1
2
input03-easy AC 28 ms 1196 KB
1
2
input04 AC 216 ms 16384 KB
2
input05 AC 140 ms 15904 KB
2
input06 AC 188 ms 15572 KB
2
input07 AC 238 ms 16564 KB
2
input08 AC 175 ms 22124 KB
2
input09 AC 248 ms 23444 KB
2
input10 AC 251 ms 24252 KB
2
input11 AC 184 ms 28000 KB
2
input12 AC 179 ms 28552 KB
2
input13 AC 21 ms 11820 KB
2
input14 AC 20 ms 11900 KB
2