#include<bits/stdc++.h>
using namespace std;
pair<int, int> finde(vector<vector<pair<int,int>>> &c, int x, int y){
int x1=x, y1=y;
pair<int,int> temp={x1,y1};
pair<int,int> temp2=c[x1][y1];
while(temp2!=temp){
int t=c[x1][y1].first;
y1=c[x1][y1].second;
x1=t;
temp={x1,y1};
temp2=c[x1][y1];
}
int px=x, py=y;
temp={x,y};
temp2=c[x][y];
while(temp2!=temp){
int t=c[x][y].first;
y=c[x][y].second;
x=t;
c[px][py]={x1, y1};
px=x;
py=y;
temp={x,y};
temp2=c[x][y];
}
return {x1, y1};
}
void unionize(vector<vector<pair<int,int>>> &c,vector<vector<int>> &s, pair<int, int> a, pair<int, int> b){
a=finde(c, a.first, a.second);
b=finde(c, b.first, b.second);
if(a==b) return;
if(s[a.first][a.second]<s[b.first][b.second]){
auto ccc = a;
a=b;
b=ccc;
}
s[a.first][a.second]+=s[b.first][b.second];
c[b.first][b.second]=a;
return;
}
int main(){
int n, m;
cin >> n >> m;
bool a[n+2][m+2];
vector<vector<pair<int, int>>> c(n+2);
vector<vector<int>> s(n+2);
for(int i = 0; i<n+2; i++){
c[i].resize(m+2);
s[i].resize(m+2);
}
for(int i = 0; i < n+2; i++){
c[i][0]={2,0};
c[i][m+1]={0,2};
a[i][0]=1;
a[i][m+1]=1;
s[i][0]=1;
s[i][m+1]=1;
}
s[0][1]=n+m-1;
s[1][0]=n+m-1;
for(int i = 0; i < m+2; i++){
c[0][i]={0,2};
c[n+1][i]={2,0};
a[0][i]=1;
a[n+1][i]=1;
s[0][i]=1;
s[n+1][i]=1;
}
a[0][0]=0;
a[1][0]=0;
a[0][1]=0;
a[n+1][m]=0;
a[n][m+1]=0;
a[n+1][m+1]=0;
for(int i = 1; i < n+1; i++){
for(int j = 1 ;j < m+1; j++){
a[i][j]=0;
s[i][j]=1;
c[i][j]={i, j};
}
}
for(int i = 1; i < n+1; i++){
for(int j = 1 ;j < m+1; j++){
bool temp;
cin >> temp;
if(temp){
a[i][j]=1;
pair<int, int> aaa[8]={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
for(int ii = 0; ii < 8; ii++){
if(a[aaa[ii].first+i][aaa[ii].second+j]){
unionize(c, s, {aaa[ii].first+i, aaa[ii].first+i}, {i, j});
}
}
}
}
}
int q;
cin >> q;
for(int i = 0; i < q; i++){
int x,y;
cin >> x>>y;
bool c0=0, c1=0;
pair<int, int> l0, l1;
l0=finde(c, 0, 2);
l1=finde(c, 2, 0);
pair<int, int> aaa[8]={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
for(int j = 0; j < 8; j++){
if(a[aaa[j].first+x][aaa[j].second+y]){
pair<int, int> l = finde(c, aaa[j].first+x, aaa[j].second+y);
if(l==l0){
// cout << "0: " << aaa[j].first+x << '/' <<aaa[j].second+y << '\n';
c0=1;
}
if(l==l1){
// cout << "1: " << aaa[j].first+x << '/' <<aaa[j].second+y << '\n';
c1=1;
}
//cout << '\n';
}
}
if(c0&&c1){
cout << "0\n";
continue;
}
for(int ii = 0; ii < 8; ii++){
if(a[aaa[ii].first+x][aaa[ii].second+y]){
unionize(c, s, {aaa[ii].first+x, aaa[ii].first+y}, {x, y});
}
a[x][y]=1;
}
cout << "1\n";
}
/*
for(int i = 0; i < n+2; i++){
for(int j =0 ;j < m+2; j++){
if(a[i][j]){
auto temp = finde(c, i, j);
cout << temp.first<<'/' <<temp.second<< ' ';
}else{
cout << "*** ";
}
}
cout << '\n';
}*/
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
