fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define sz(a) (int)a.size()
  5. #define all(a) begin(a),end(a)
  6. using vi = vector<int>;
  7. const int mxN = (int)1501;
  8. const int MXN = mxN*mxN;
  9. int X[] = {-1,0,1,0};
  10. int Y[] = {0,1,0,-1};
  11.  
  12. string a[mxN];
  13. bitset<mxN> vis[4][mxN];
  14. int n, m, q, sx, sy, bx, by;
  15.  
  16. int dfs_tim;
  17. vi v, adj[MXN];
  18. bitset<MXN> BCC;
  19. int st[MXN], low[MXN];
  20.  
  21. int node(int x, int y){ return x*1500+y+1; }
  22.  
  23. void ae(vi adj[], int a, int b, bool undi=1){
  24. 	adj[a].pb(b); if(undi) adj[b].pb(a);
  25. }
  26.  
  27. int ST;
  28. void dfsCut(int s, int p){ // fix
  29. 	if(!sz(adj[s])){ if(!p) BCC[s]=1; return; }
  30. 	st[s] = low[s] = ++dfs_tim; v.pb(s);
  31. 	int num = 0, child = 0, x;
  32. 	for(auto u : adj[s]){
  33. 		if(u==p) continue;
  34. 		if(!st[u]){
  35. 			dfsCut(u,s); child++;
  36. 			low[s]=min(low[s],low[u]);
  37. 			if(low[u] >= st[s]){
  38. 				num++; if(!p) BCC[s]=1;
  39. 				vi xd; xd.clear();
  40. 				bool good = 0;
  41. 				do{
  42. 					x=v.back(); v.pop_back();
  43. 					if(x==ST) good=1;
  44. 					if(!p) BCC[x]=1;
  45. 					else xd.pb(x);
  46. 				} while(x!=u);
  47. 				if(good)for(auto u : xd)BCC[u]=1;
  48. 			}
  49. 		}
  50. 		else low[s]=min(low[s],st[u]);
  51. 	}
  52. }
  53.  
  54. bool canGo(int sx, int sy, int dx, int dy, int bx, int by){
  55. 	if(sx<0 or sy<0 or sx>=n or sy>=m or a[sx][sy]=='#') return 0;
  56. 	if(dx<0 or dy<0 or dx>=n or dy>=m or a[dx][dy]=='#') return 0;
  57. 	int a = node(sx,sy), b = node(dx,dy), c = node(bx,by);
  58. 	return BCC[a] and BCC[b]; // doesn't work right
  59. }
  60.  
  61. void recur(int x, int y, int d){
  62. 	int mx = x+X[d], my = y+Y[d];
  63. 	if(x<0 or y<0 or x>=n or y>=m) return;
  64. 	if(mx<0 or my<0 or mx>=n or my>=m) return;
  65. 	if(a[x][y]=='#' or a[mx][my]=='#' or vis[d][x][y]) return;
  66. 	vis[d][x][y] = 1; recur(x+X[(d+2)%4],y+Y[(d+2)%4],d);
  67. 	for(int nd = 0; nd < 4; nd++){
  68. 		int nx = x+X[nd], ny = y+Y[nd];
  69. 		if(canGo(mx,my,nx,ny,x,y)) recur(x,y,nd);
  70. 	}
  71. }
  72.  
  73. int main(){
  74. 	ios_base::sync_with_stdio(false); cin.tie(0);
  75. 	ifstream cin("pushabox.in");
  76. 	ofstream cout("pushabox.out");
  77. 	cin >> n >> m >> q;
  78. 	for(int i = 0; i < n; i++){
  79. 		cin >> a[i];
  80. 		for(int j = 0; j < m; j++){
  81. 			if(a[i][j]=='A') sx=i,sy=j;
  82. 			if(a[i][j]=='B') bx=i,by=j;
  83. 		}
  84. 	}
  85. 	for(int i = 0; i < n; i++){
  86. 		for(int j = 0; j < n; j++){
  87. 			if(a[i][j]=='#') continue;
  88. 			for(int d = 0; d < 4; d++){
  89. 				int ni = i+X[d], nj = j+Y[d];
  90. 				if(ni<0 or nj<0 or ni>=n or nj>=m or a[ni][nj]=='#') continue;
  91. 				ae(adj,node(i,j),node(ni,nj),0);
  92. 			}
  93. 		}
  94. 	}
  95. 	dfsCut(node(sx,sy),0);
  96. 	for(int d = 0; d < 4; d++)
  97. 		if(canGo(sx,sy,bx+X[d],by+Y[d],bx,by))
  98. 			recur(bx,by,d);
  99. 	while(q--){
  100. 		int x, y, ok = 0; cin >> x >> y; x--, y--;
  101. 		for(int i = 0; i < 4; i++) ok|=vis[i][x][y];
  102. 		cout << (ok?"YES":"NO") << "\n";
  103. 	}
  104. }
  105.  
Success #stdin #stdout 0.02s 57696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZSEDnP
Usaco Plat Push A Box
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!