oj.uz

답안 #390962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390962 2021-04-17T12:44:50 Z keta_tsimakuridze Furniture (JOI20_furniture) C++14
0 / 100
 5000 ms 2124 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=1005,mod=1e9+7;
int t,a[N][N],p[N][N][2],c[N][N][2],n,m,s[N][N][2],q;
set<int> st[N];
bool ok(int x,int y){
	if(min(x,y)<1 || x>n || y>m) return 0;
	return 1;
}
void dfs1(int x,int y,int c){
	if(p[x][y][c]) return;
	p[x][y][c] = 1;
	if(ok(x+1,y) && a[x+1][y]!=1) dfs1(x+1,y,0);
	if(ok(x,y+1) && a[x][y+1]!=1) dfs1(x,y+1,1);
}
void dfs2(int x,int y,int c){
	if(s[x][y][c]) return;
	s[x][y][c] = 1;
	if(ok(x-1,y) && a[x-1][y]!=1) dfs2(x-1,y,0);
	if(ok(x,y-1) && a[x][y-1]!=1) dfs2(x,y-1,1);
}
void go(int x,int y,int b){
	if(!c[x][y][b] && !c[x][y][1-b]) return;
	c[x][y][b]--;
	if(!c[x][y][b^1]) st[y].erase(x);
	if(ok(x+1,y) && a[x+1][y]!=1) go(x+1,y,0);
	if(ok(x,y+1) && a[x][y+1]!=1) go(x,y+1,1);
}
 main(){
	// t=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dfs1(1,1,0);
	dfs2(n,m,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){ 
			if(max(p[i][j][0],p[i][j][1]) && max(s[i][j][0],s[i][j][1])) c[i][j][0] = s[i][j][0] ,
																		  c[i][j][1] = s[i][j][1];
			if(c[i][j][1]) st[j].insert(i);
		}
	}
	cin >>q;
	while(q--){
		int x,y;
		cin >> x >> y;
		if(st[y].size() && (*st[y].begin()!=x || *--st[y].end()!=x) ) {
			cout<<1<<endl;
			go(x,y,0);
		}
		else cout<<0<<endl;
	}
}

Compilation message

furniture.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 |  main(){
      |       ^

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5056 ms 2124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5056 ms 2124 KB Time limit exceeded
2 Halted 0 ms 0 KB -