Submission #74143

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct unionfind{
int n;
vector<int> parent;
vector<int> num;
unionfind(int n):n(n),parent(vector<int>(n)),num(vector<int>(n,1)){
for(int i = 0; i < n; i++) parent[i] = i;
}
int find(int n){
if (parent[n] == n) return n;
parent[n] = find(parent[n]);
return parent[n];
}
int merge(int n,int m){
n = find(n);
m = find(m);
if (n==m) return n;
if (num[n]>num[m]) return merge(m,n);
parent[m] = n;
num[n] += num[m];
return n;
}
int getnum(int n){
return num[find(n)];
}
};
template< typename T >
struct edge{
int from,to;
T cost;
edge(int from,int to, T cost):from(from),to(to),cost(cost){};
edge &operator=(const int& x){
to = x;
return *this;
}
};
template< typename T >
struct graph{
int n;
vector<vector<edge<T>>> e;
graph(int n):n(n),e(n){}
void addedge(int from,int to,T cost){
e[from].emplace_back(from,to,cost);
}
vector<edge<T>> &operator[](int i) {
return e[i];
}
};
template< typename T >
vector<T> dijkstra(graph<T>& g, int st){
int n = g.n;
using pt = pair<T,int>;
vector<T> dist(n,-1);
dist[st] = 0;
priority_queue<pt, vector<pt>, greater<pt>>que;
que.emplace(0,st);
while(que.size()){
int ni;
T cost;
tie(cost,ni) = que.top();
que.pop();
if(dist[ni]<cost&&dist[ni]!=-1) continue;
for(edge<T> itr:g[ni]){
int nxt = itr.to;
if(dist[nxt]>cost+itr.cost||dist[nxt]==-1){
dist[nxt] = cost + itr.cost;
que.emplace(dist[nxt],nxt);
}
}
}
return dist;
};
int h,w,q;
vector<string> m;
unionfind uf(1);
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
void merge(int i,int j){
for(int k = 0;k<4;k++){
int ni = i + dx[k];
int nj = j + dy[k];
if(ni<0||ni>=h||nj<0||nj>=w) continue;
if(m[ni][nj]=='#') uf.merge(i*w+j,ni*w+nj);
}
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin>>h>>w>>q;
uf = unionfind(w*h);
m = vector<string>(h);
for(int i = 0;i<h;i++) cin>>m[i];
for(int i = 0;i<h;i++)for(int j = 0;j<w;j++)if(m[i][j]=='#')merge(i,j);
while(q--){
int t,i,j;
cin>>t>>i>>j;
i--;j--;
if(t==0){
m[i][j] = '#';
merge(i,j);
}else{
if(m[i][j]=='.') cout<<0<<endl;
else cout<<uf.getnum(i*w+j)<<endl;
}
}
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 momoyuu
投稿日時 2023-03-23 19:42:21
言語 C++17
状態 Accepted
得点 10
ソースコード長 2760 Byte
最大実行時間 1093 ms
最大メモリ使用量 67068 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 35 ms 604 KB
1
2
input-sample2 AC 29 ms 560 KB
1
2
input01-easy AC 37 ms 764 KB
1
2
input02-easy AC 21 ms 856 KB
1
2
input03-easy AC 20 ms 932 KB
1
2
input04 AC 578 ms 14180 KB
2
input05 AC 391 ms 17532 KB
2
input06 AC 528 ms 22260 KB
2
input07 AC 612 ms 28204 KB
2
input08 AC 640 ms 37524 KB
2
input09 AC 656 ms 44588 KB
2
input10 AC 653 ms 51140 KB
2
input11 AC 1093 ms 60772 KB
2
input12 AC 685 ms 67068 KB
2
input13 AC 32 ms 58268 KB
2
input14 AC 26 ms 58220 KB
2