Submission #1326105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326105		JuanJL	Furniture (JOI20_furniture)	C++20	5 / 100	8 ms	1336 KiB

furniture

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

#ifdef D
	#define debug(x) cout << x
#else
	#define debug(x) //nothing
#endif

const int MAXN = 100+5;

vector<pair<ll,ll>> oper = {{0,1},{1,0}};
vector<pair<ll,ll>> roper = {{0,-1},{-1,0}};

ll n,m;
vector<vector<ll>> mapa;
bool vis[MAXN][MAXN];

//vector<pair<ll,ll>> llega[MAXN][MAXN];

bool rright[MAXN][MAXN];
bool down[MAXN][MAXN];
bool lleft[MAXN][MAXN];
bool up[MAXN][MAXN];

bool dfs(ll i, ll j){
	if(vis[i][j]) return (rright[i][j]||down[i][j]);
	vis[i][j]=true;
	if(i==n-1 && j==m-1) rright[i][j]=down[i][j]=true;
	
	for(auto o:oper) if(i+o.fst<n && j+o.snd<m){
		if(mapa[i+o.fst][j+o.snd]==0 && dfs(i+o.fst,j+o.snd)){
			if(o.snd==1) rright[i][j]=true;
			else down[i][j]=true;
		}
	}
	return (rright[i][j]||down[i][j]);
}

bool sdfs(ll i, ll j){
	if(vis[i][j]) return (lleft[i][j]||up[i][j]);
	vis[i][j]=true;
	if(i==0 && j==0) return lleft[i][j]=up[i][j]=true;

	for(auto o:roper) if(i+o.fst>=0 && j+o.snd>=0){
		if(mapa[i+o.fst][j+o.snd]==0 && sdfs(i+o.fst,j+o.snd)){
			if(o.snd==-1) lleft[i][j]=true;
			else up[i][j]=true;
		}
	}
	return (lleft[i][j]||up[i][j]);
}

bool yes=false;

vector<pair<pair<ll,ll>,ll>> era;

void rdfs(ll i, ll j){
	if(i==0 && j==0){ yes=true; return; }	
	debug("rdfs "<<i<<" "<<j<<'\n');

	bool parc = true;
	for(auto o:roper) if(i+o.fst>=0 && j+o.snd>=0){

		if(o.snd==-1 && rright[i+o.fst][j+o.snd]){
			rright[i+o.fst][j+o.snd]=false;
			parc=false;
			era.pb({{i+o.fst,j+o.snd},0});
		}

		if(o.fst==-1 && down[i+o.fst][j+o.snd]){
			down[i+o.fst][j+o.snd]=false;
			parc=false;
			era.pb({{i+o.fst,j+o.snd},1});
		}

		if(!rright[i+o.fst][j+o.snd] && !down[i+o.fst][j+o.snd] && !parc){
			rdfs(i+o.fst,j+o.snd);
		}
	}
}

void rrdfs(ll i, ll j){
	if(i==n-1 && j==m-1) return;
	debug("rrdfs "<<i<<" "<<j<<'\n');

	bool parc = true;
	for(auto o:oper)if(i+o.fst<n && j+o.snd<m){
		if(o.snd==1 && lleft[i+o.fst][j+o.snd]){
			lleft[i+o.fst][j+o.snd]=false;
			parc=false;
		}
		if(o.fst==1 && up[i+o.fst][j+o.snd]){
			up[i+o.fst][j+o.snd]=false;
			parc=false;
		}

		if(!lleft[i+o.fst][j+o.snd] && !up[i+o.fst][j+o.snd] && !parc){
			rrdfs(i+o.fst,j+o.snd);
		}
	}
}

int main(){ FIN;
	cin>>n>>m;
	mapa.clear();
	mapa.resize(n,vector<ll>(m,0));
	forn(i,0,n){
		forn(j,0,m){
			cin>>mapa[i][j];
		}
	}

	dfs(0,0);
	mset(vis,false);
	sdfs(n-1,m-1);
	forn(I,0,n){
							forn(J,0,m){
								debug(mapa[I][J]<<" ("); debug(rright[I][J]<<","<<down[I][J]<<","<<lleft[I][J]<<","<<up[I][J]); debug(") ");
							} debug('\n');
						}
			
	ll q; cin>>q;
	forn(i,0,q){
		ll x,y; cin>>x>>y; x--; y--;
		if(mapa[x][y]!=1){
			mapa[x][y]=1;
			/*mset(vis,false);
			forn(I,0,n) forn(J,0,n) llega[I][J].clear();
			if(!dfs(0,0)) mapa[x][y]=0, cout<<0<<'\n';
			else cout<<1<<'\n';*/
			ll cnt = 0;
			ll nx = x-1; ll ny = y+1;
			while(nx>=0 && ny<m){
				debug("viendo diag "<<nx<<" "<<ny<<'\n');
				if((rright[nx][ny] || down[nx][ny] ) && (lleft[nx][ny] || up[nx][ny])){
					cnt++;
				}
				nx--;
				ny++;
			}

			nx=x+1; ny=y-1;
			while(nx<n && ny>=0){
				debug("viendo diag "<<nx<<" "<<ny<<'\n');
				if((rright[nx][ny] || down[nx][ny] ) && (lleft[nx][ny] || up[nx][ny])){
									cnt++;
								}
				nx++;
				ny--;
			}
			if(cnt>0){
				rdfs(x,y);
				rrdfs(x,y);
				down[x][y]=rright[x][y]=up[x][y]=lleft[x][y]=false;
				cout<<1<<'\n';
			}else{
				cout<<0<<'\n';
			}

			
			forn(I,0,n){
										forn(J,0,m){
											debug(mapa[I][J]<<" ("); debug(rright[I][J]<<","<<down[I][J]<<","<<lleft[I][J]<<","<<up[I][J]); debug(") ");
										} debug('\n');
									}
							
		}else{
			cout<<0<<'\n';
		}
	}
	
	return 0;
}

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