ec1117

Untitled

Oct 26th, 2020 (edited)
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. struct BCC {
  2.     vector<vpi> adj; vpi ed;
  3.     vector<vi> comps; // edges for each bcc
  4.     int N, ti = 0; vi disc, st;
  5.     void init(int _N) { N = _N; disc.rsz(N), adj.rsz(N); }
  6.     void ae(int x, int y) {
  7.             adj[x].eb(y,sz(ed)), adj[y].eb(x,sz(ed)), ed.eb(x,y); }
  8.     int dfs(int x, int p = -1) { // return lowest disc
  9.             int low = disc[x] = ++ti;
  10.             trav(e,adj[x]) if (e.s != p) {
  11.                             if (!disc[e.f]) {
  12.                                     st.pb(e.s); // disc[x] < LOW -> bridge
  13.                                     int LOW = dfs(e.f,e.s); ckmin(low,LOW);
  14.                                     if (disc[x] <= LOW) { // get edges in bcc
  15.                                             comps.eb(); vi& tmp = comps.bk; // new bcc
  16.                                             for (int y = -1; y != e.s; )
  17.                                                     tmp.pb(y = st.bk), st.pop_back();
  18.                                     }
  19.                             } else if (disc[e.f] < disc[x]) // back-edge
  20.                                     ckmin(low,disc[e.f]), st.pb(e.s);
  21.                     }
  22.             return low;
  23.     }
  24.     void gen() { F0R(i,N) if (!disc[i]) dfs(i);  }
  25. };
  26.  
  27. BCC bcc;
  28. int n,m,q2, gr[MX], cnt;
  29. bool v[MX][MX][4], v2[MX][MX], grid[MX][MX];
  30. pi st,ed;
  31. int calc[MX*MX*2];
  32.  
  33. int tr(int a, int b){return n*a+b;}
  34. int tr(int a, int b, int c){return (n*a+b)*4+c;}
  35. bool legal(int a, int b){return (a>=0 && b>=0);}
  36.  
  37. void dumbdfs(int x, int y){
  38.         For(i,4){
  39.                 int nx=x+xd[i],ny=y+yd[i];
  40.                 if(nx==ed.f && ny==ed.s)continue;
  41.                 if(legal(nx,ny) && grid[nx][ny] && !v2[nx][ny]){
  42.                         v2[nx][ny]=1;
  43.                         dumbdfs(nx,ny);
  44.                 }
  45.         }
  46. }
  47.  
  48. int main() {
  49.         setIO();
  50.         re(n,m,q2);
  51.         bcc.init(2*MX*MX);
  52.         For(i,n){
  53.                 string s;re(s);
  54.                 For(j,m){
  55.                         grid[i][j]= (s[j]=='.' || s[j]=='A' || s[j]=='B');
  56.                         if(s[j]=='A')st=mp(i,j);
  57.                         if(s[j]=='B')ed=mp(i,j);
  58.                 }
  59.         }
  60.         For(i,n)For(j,m){if(!grid[i][j])continue;
  61.                 if(grid[i+1][j]){
  62.                         bcc.ae(tr(i,j),tr(i+1,j));
  63.                         calc[tr(i,j,2)]=cnt;
  64.                         calc[tr(i+1,j,0)]=cnt;
  65.                         cnt++;
  66.                 }
  67.                 if(grid[i][j+1]){//careful here
  68.                         bcc.ae(tr(i,j),tr(i,j+1));
  69.                         calc[tr(i,j,3)]=cnt;
  70.                         calc[tr(i,j+1,1)]=cnt;//nums
  71.                         cnt++;
  72.                 }
  73.         }
  74.         bcc.gen();
  75.         For(i,sz(bcc.comps)){
  76.                 trav(x,bcc.comps[i])gr[x]=i+1;
  77.         }
  78.  
  79.         dumbdfs(st.f,st.s);
  80.  
  81.         queue<pii> q;
  82.         For(i,4){
  83.                 int nx=ed.f+xd[i], ny=ed.s+yd[i];
  84.                 int tx=ed.f, ty=ed.s;
  85.                 if(legal(nx,ny) && v2[nx][ny]){
  86.                         q.push(mp(mp(tx,ty),(i+2)%4));
  87.                         v[tx][ty][(i+2)%4]=1;
  88.                 }
  89.         }
  90.         while(!q.empty()){
  91.                 pii x=q.front();q.pop();
  92.                 int ox=x.f.f+xd[x.s], oy=x.f.s+yd[x.s];
  93. //                dbg(x,ox,oy,legal(ox,oy),grid[ox][oy],v[ox][oy][x.s]);
  94.                 if(legal(ox,oy) && grid[ox][oy] && !v[ox][oy][x.s]){
  95.                         v[ox][oy][x.s]=1;
  96.                         q.push(mp(mp(ox,oy),x.s));
  97.                 }
  98.                 For(i,4){
  99.                         int nx=x.f.f, ny=x.f.s;
  100.                         if(!v[nx][ny][i] && gr[calc[tr(nx,ny,x.s)]]==gr[calc[tr(nx,ny,i)]]){
  101. //                                if(nx==2 && ny==2 && i==2)dbg("hi",nx,ny,x,i,calc[tr(nx,ny,x.s)],calc[tr(nx,ny,i)] );
  102.                                 v[nx][ny][i]=1;
  103.                                 q.push(mp(mp(nx,ny),i));
  104.                         }
  105.                 }
  106.         }
  107.  
  108.         For(i,q2){
  109.                 int a, b;re(a,b);a--;b--;
  110.                 ps((v[a][b][0]||v[a][b][1]||v[a][b][2]||v[a][b][3])?"YES":"NO");
  111.         }
  112.         dbg(bcc.comps);
  113. // you should actually read the stuff at the bottom
  114. }
Add Comment
Please, Sign In to add comment