ec1117

Untitled

Mar 31st, 2021
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.16 KB | None | 0 0
  1. #pragma GCC target ("avx2")
  2. // #pragma GCC optimization ("O3")
  3. // #pragma GCC optimization ("unroll-loops")
  4. #include "bits/stdc++.h"
  5. using namespace std;
  6.  
  7. #define mp make_pair
  8. #define f first
  9. #define s second
  10. #define FOR(i,a,b) for(int i=a;i<b;i++)
  11. #define For(i,b) FOR(i,0,b)
  12. #define trav(a,b) for(auto& a:b)
  13. #define vi vector<int>
  14. #define vpi vector<pi>
  15. #define vs vector<string>
  16. #define pb push_back
  17. #define bk back()
  18. #define ins insert
  19. #define pi pair<int,int>
  20. #define ll long long
  21. #define sz(x) (int) x.size()
  22. #define all(x) x.begin(),x.end()
  23. #define nl '\n'
  24. #define AR array<int,3>
  25.  
  26. const int MX=15e2+5;
  27. const int MX2=23e5+5;
  28. const int MOD=1e9+7;
  29.  
  30. void dbg(){
  31.     cerr<<endl;
  32. }
  33. template<class A,class... B> void dbg(A a, B... b){
  34.     cerr<<a;
  35.     if(sizeof...(b))cerr<<", ";
  36.     dbg(b...);
  37. }
  38.  
  39. template<class T> bool ckmin(T& a,const T& b){
  40.     if(b<a){
  41.         a=b; return true;
  42.     }
  43.     return false;
  44. }
  45. template<class T> bool ckmax(T& a, T& b){
  46.     if(b>a){
  47.         a=b; return true;
  48.     }
  49.     return false;
  50. }
  51.  
  52. int n,m,q;
  53. int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
  54. bool conn[MX][MX][4][4];
  55. vs g;
  56.  
  57. struct BCC{
  58.     vi adj[MX2];
  59.     vector<vi> comps;
  60.     int low[MX2];
  61.     int dep[MX2];
  62.     int N;
  63.     vi stk;
  64.     void ae(int a, int b){
  65.         adj[a].pb(b);
  66.         adj[b].pb(a);
  67.     }
  68.     void init(int _N){
  69.         N=_N;
  70.         memset(low,MOD,sizeof low);
  71.         memset(dep,-1,sizeof dep);
  72.     }
  73.     void dfs(int n, int p){
  74.         dbg(n,p);
  75.         stk.pb(n);
  76.         low[n]=dep[n];
  77.         trav(x,adj[n])if(x!=p){
  78.             if(dep[x]==-1){
  79.                 dep[x]=dep[n]+1;
  80.                 dfs(x,n);
  81.                 ckmin(low[n],low[x]);
  82.                 if(low[x]==dep[n]){
  83.                     comps.pb({});
  84.                     while(sz(stk) && stk.bk!=n){
  85.                         comps.bk.pb(stk.bk);
  86.                         stk.pop_back();
  87.                     }
  88.                     comps.bk.pb(n);
  89.                 }
  90.             } else if(dep[x]<dep[n]){
  91.                 ckmin(low[n],dep[x]);
  92.             }
  93.         }
  94.         if(low[n]==dep[n]){
  95.             stk.pop_back();
  96.         }
  97.     }
  98.     void gen(){
  99.         For(i,N)if(dep[i]==-1 && sz(adj[i]))stk.clear(),dep[i]=0,dfs(i,i);
  100.     }
  101. } bcc;
  102.  
  103. bool leg(int a, int b){
  104.     return a>=0 && b>=0 && a<n && b<m;
  105. }
  106. int opp(int a){
  107.     return (a+2)%4;
  108. }
  109. bool vis[MX][MX][4];//where person is relative to box
  110. bool vis2[MX][MX];
  111. vi TMP[MX][MX];
  112.  
  113. int main(){
  114.     cin.tie(0)->sync_with_stdio(0);//HI
  115.     freopen("pushabox.in","r",stdin);
  116.     freopen("pushabox.out","w",stdout);
  117.     cin>>n>>m>>q;
  118.     dbg(n,m,q);
  119.     For(i,n){
  120.         string S;cin>>S;
  121.         g.pb(S);
  122.     }
  123.     bcc.init(n*m);
  124.     pi st,bx;
  125.     For(i,n)For(j,m)if(g[i][j]!='#'){
  126.         if(g[i][j]=='A')st={i,j};
  127.         if(g[i][j]=='B')bx={i,j};
  128.         For(k,4){
  129.             int nx=i+dx[k],ny=j+dy[k];
  130.             if(leg(nx,ny) && g[nx][ny]!='#'){
  131.                 bcc.ae(i*m+j,nx*m+ny);
  132.             }
  133.         }
  134.     }
  135.     dbg("HI");
  136.     bcc.gen();
  137.     dbg("HI");
  138.     trav(x,bcc.comps){
  139.         vpi tmp2;
  140.         trav(y,x){
  141.             int i=y/m,j=y%m;
  142.             For(k,4){
  143.                 int nx=i+dx[k],ny=j+dy[k];
  144.                 if(leg(nx,ny) && g[nx][ny]!='#'){
  145.                     tmp2.pb({nx,ny});
  146.                     TMP[nx][ny].pb(opp(k));
  147.                 }
  148.             }
  149.         }
  150.         trav(y,tmp2)if(sz(TMP[y.f][y.s])){
  151.             vi& tmp=TMP[y.f][y.s];
  152.             For(i,sz(tmp)){
  153.                 For(j,sz(tmp)){
  154.                     conn[y.f][y.s][tmp[i]][tmp[j]]=true;
  155.                 }
  156.             }
  157.             TMP[y.f][y.s].clear();
  158.         }
  159.     }
  160.     dbg("HI");
  161.     queue<pi> q1;
  162.     q1.push({st.f,st.s});
  163.     vis2[st.f][st.s]=true;
  164.     while(sz(q1)){
  165.         pi x=q1.front();q1.pop();
  166.         For(k,4){
  167.             int nx=x.f+dx[k],ny=x.s+dy[k];
  168.             if(leg(nx,ny) && g[nx][ny]=='.' && !vis2[nx][ny]){
  169.                 vis2[nx][ny]=true;
  170.                 q1.push({nx,ny});
  171.             }
  172.         }
  173.     }
  174.     queue<AR> q2;
  175.     For(k,4){
  176.         int nx=bx.f+dx[k],ny=bx.s+dy[k];
  177.         if(leg(nx,ny) && vis2[nx][ny]){
  178.             vis[bx.f][bx.s][k]=true;
  179.             q2.push({bx.f,bx.s,k});
  180.         }
  181.     }
  182.     dbg("HI");
  183.     while(sz(q2)){
  184.         AR x=q2.front();q2.pop();
  185.         //switch dir
  186.         For(i,4){
  187.             if(conn[x[0]][x[1]][x[2]][i] && !vis[x[0]][x[1]][i]){
  188.                 vis[x[0]][x[1]][i]=true;
  189.                 q2.push({x[0],x[1],i});
  190.             }
  191.         }
  192.         //push forward?
  193.         int dir=opp(x[2]);
  194.         int nx=x[0]+dx[dir],ny=x[1]+dy[dir];
  195.         if(leg(nx,ny) && g[nx][ny]!='#' && !vis[nx][ny][x[2]]){
  196.             vis[nx][ny][x[2]]=true;
  197.             q2.push({nx,ny,x[2]});
  198.         }
  199.     }
  200.     dbg("HI");
  201.  
  202.     bool good[n][m];
  203.     For(i,n){
  204.         For(j,m){
  205.             good[i][j]=(vis[i][j][0]||vis[i][j][1]||vis[i][j][2]||vis[i][j][3]);
  206.             // cout<<(good[i][j]?"X":".");
  207.         }
  208.         // cout<<endl;
  209.     }
  210.     good[bx.f][bx.s]=true;
  211.     For(i,q){
  212.         int x,y;cin>>x>>y;x--;y--;
  213.         if(!i)dbg(x,y);
  214.         cout<<(good[x][y]?"YES":"NO")<<'\n';//endl
  215.     }
  216. }
Advertisement
Add Comment
Please, Sign In to add comment