제출 #600190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600190		ignus	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	468 KiB

furniture

#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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95