Submission #488048

#	Time	Username	Problem	Language	Result	Execution time	Memory
488048		AdamGS	Furniture (JOI20_furniture)	C++14	0 / 100	7 ms	1484 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7, INF=1e9+7;
int T[LIM][LIM], lst[LIM][LIM], uzyte[LIM][LIM], ans[LIM*LIM], n, m;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	rep(i, n) rep(j, m) {
		T[i][j]=INF;
		int a;
		cin >> a;
		if(a) T[i][j]=-1;
	}
	int q;
	cin >> q;
	rep(i, q) {
		ans[i]=1;
		int a, b;
		cin >> a >> b; --a; --b;
		T[a][b]=i;
	}
	priority_queue<pair<pair<pair<int,int>,int>,pair<int,int>>>pq;
	pq.push({{{T[0][0], INF}, 0}, {0, 0}});
	while(!pq.empty()) {
		int x=pq.top().st.st.st, y=pq.top().st.nd, z=pq.top().st.st.nd;
	 	int a=pq.top().nd.st, b=pq.top().nd.nd; 
		pq.pop();
		if(lst[a][b]) continue;
		lst[a][b]=y;
		if(a<n-1) pq.push({{{T[a+1][b], min(z, T[a][b])}, 1}, {a+1, b}});
		if(b<m-1) pq.push({{{T[a][b+1], min(z, T[a][b])}, 2}, {a, b+1}});
	}
	int a=n-1, b=m-1;
	while(a || b) {
		uzyte[a][b]=1;
		if(lst[a][b]==1) --a;
		else --b;
	}
	uzyte[0][0]=1;
	rep(i, n) rep(j, m) if(uzyte[i][j]) {
		if(T[i][j]<INF) ans[T[i][j]]=0;
	}
	rep(i, q) cout << ans[i] << '\n';
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:32:7: warning: unused variable 'x' [-Wunused-variable]
   32 |   int x=pq.top().st.st.st, y=pq.top().st.nd, z=pq.top().st.st.nd;
      |       ^

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