fork download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #pragma GCC optimize ("O3")
  5. #pragma GCC target ("sse4")
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9.  
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Tree;
  13.  
  14. #define sz(x) (int)(x).size()
  15. #define ll long long
  16. #define ld long double
  17. #define mp make_pair
  18. #define pb push_back
  19. #define eb emplace_back
  20. #define pii pair <int, int>
  21. #define vi vector<int>
  22. #define f first
  23. #define s second
  24. #define lb lower_bound
  25. #define ub upper_bound
  26. #define all(x) x.begin(), x.end()
  27. #define vpi vector<pair<int, int>>
  28.  
  29. #define f0r(i,a) for(int i=0;i<a;i++)
  30. #define f1r(i,a,b) for(int i=a;i<b;i++)
  31.  
  32. #define read1(a) int a; scanf("%d", &a)
  33. #define read2(a,b) int a,b; scanf("%d %d", &a, &b)
  34. #define read3(a,b,c) int a,b,c; scanf("%d %d %d", &a, &b, &c)
  35. #define read(n,arr) int arr[n]; f0r(i,n){ scanf("%d", &arr[i]); }
  36. #define print1(a) printf("%d \n", a)
  37. #define print2(a, b) printf("%d %d \n", a, b)
  38. #define print3(a, b, c) printf("%d %d %d \n", a, b, c)
  39. #define print(v) for (int i : v) { printf("%d ", i); } printf("\n")
  40.  
  41. #define debug printf("asdf\n");
  42. #define newl printf("\n");
  43. #define usaco(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout);
  44. void fast_io(){
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(NULL);
  47.     cout.tie(NULL);
  48. }
  49. void io(string taskname){
  50.     string fin = taskname + ".in";
  51.     string fout = taskname + ".out";
  52.     const char* FIN = fin.c_str();
  53.     const char* FOUT = fout.c_str();
  54.     freopen(FIN, "r", stdin);
  55.     freopen(FOUT, "w", stdout);
  56.     fast_io();
  57. }
  58.  
  59. const int MAX = 1505;
  60. const int BIG = 2250005;
  61.  
  62. static int n, m, q;
  63.  
  64. int vis[BIG][4];
  65. int grid[MAX][MAX];
  66. int reach[BIG];
  67. //checks if location to visit is valid and inbounds and not a hay pile
  68. int valid(int x, int y){
  69.     int a = x/m;
  70.     int b = x%m;
  71.     if(y == 0){ //up
  72.         a-= 1;
  73.     }
  74.     else if(y == 2){ //down
  75.         a+= 1;
  76.     }
  77.     else if(y == 1){ // left
  78.         b-= 1;
  79.     }
  80.     else{ //right
  81.         b+= 1;
  82.     }
  83.     if(a>=0  && a<n && b>=0 && b<m && grid[a][b] == 0){ //not filled with hay
  84.          return a*m + b; //return
  85.     }
  86.     return -1;
  87. }
  88. //finds biconnected components
  89. struct BCC {
  90.     int V, ti = 0;
  91.     vector<vector<int>> adj;
  92.     vector<int> par, disc, low;
  93.     vector<vector<pair<int, int>>> fin;
  94.     vector<pair<int, int>> st;
  95.     vector<int> comp;
  96.     void init(int _V) {
  97.        V = _V;
  98.        par.resize(V), disc.resize(V), low.resize(V), adj.resize(V); comp.resize(V);
  99.        for(int i= 0 ; i<V; i++){
  100.             par[i] = disc[i] = low[i] = -1;
  101.        }
  102.     }
  103.     void addEdge(int u, int v) {
  104.        adj[u].push_back(v), adj[v].push_back(u);
  105.     }
  106.  
  107.     void BCCutil(int u) {
  108.         disc[u] = low[u] = ti++;
  109.         int child = 0;
  110.         for (int toAdd = 0; toAdd<4; toAdd++){
  111.             int i = valid(u, toAdd);
  112.             if(i == -1){
  113.                 continue;
  114.             }
  115.             if (i != par[u]) {
  116.                 if (disc[i] == -1) {
  117.                      child ++; par[i] = u;
  118.                      st.push_back({u,i});
  119.                      BCCutil(i);
  120.                      low[u] = min(low[u],low[i]);
  121.  
  122.                      if ((disc[u] == 0 && child > 1) || (disc[u] != 0 && disc[u] <= low[i])) { // checks for articulation point
  123.                          vector<pair<int, int>> tmp;
  124.                          while (st.back() != make_pair(u,i)) tmp.push_back(st.back()), st.pop_back();
  125.                          tmp.push_back(st.back()), st.pop_back();
  126.                          fin.push_back(tmp);
  127.                       }
  128.                 }
  129.                 else if (disc[i] < disc[u]) {
  130.                     low[u] = min(low[u],disc[i]);
  131.                     st.push_back({u,i});
  132.                 }
  133.             }
  134.         }
  135.     }
  136.  
  137.     void bcc() {
  138.          for(int i = 0; i<V; i++){
  139.             if (disc[i] == -1 && grid[i/m][i%m] == 0) {
  140.                  BCCutil(i);
  141.                  if (st.size()) fin.push_back(st);
  142.                  st.clear();
  143.              }
  144.          }
  145.          for(int i = 0; i<fin.size(); i++){
  146.             for(int j = 0; j<fin[i].size(); j++){
  147.                 comp[fin[i][j].f] = i;
  148.                 comp[fin[i][j].s] = i;
  149.             }
  150.          }
  151.     }
  152. };
  153.  
  154. BCC b;
  155. void bfs(int cow, int box, int dir){
  156.     if(vis[box][dir] == 1){
  157.         return;
  158.     }
  159.     //bfs
  160.     list<pii> q;
  161.     q.pb(mp(box, cow));
  162.     vis[box][dir] = 1;
  163.     while(!q.empty()){
  164.         cow = q.front().s;
  165.         box = q.front().f;
  166.         q.pop_front();
  167.         for(int i = 0; i<4; i++){
  168.             // 0 down, 1 right, 2 up, 3 left
  169.             int nxtCow = valid(box, (i+2)%4); //where cow has to be to move box in direction i
  170.             int nxtBox = valid(box, i); //the next location of the box moved in direction i
  171.             if(nxtCow == -1 || nxtBox == -1){ //checking if they are valid
  172.                 continue;
  173.             }
  174.             if((b.comp[cow] != b.comp[nxtCow])){ //seeing if it's possible for the cow to move to that new location
  175.                 continue;
  176.             }
  177.             if(vis[nxtBox][i] == 1){
  178.                 continue;
  179.             }
  180.             //adding to queue
  181.             vis[nxtBox][i] = 1;
  182.             q.push_back(mp(nxtBox, box));
  183.  
  184.         }
  185.     }
  186. }
  187.  
  188. void bfs1(int cow, int box){//bfs to find where cow can be around the initial position of box
  189.     list<int> q;
  190.     q.pb(cow);
  191.     reach[cow] =1;
  192.     while(!q.empty()){
  193.         int s = q.front();
  194.         q.pop_front();
  195.         f0r(i, 4){
  196.             int nxt = valid(s, i);
  197.             if(nxt != -1 && nxt  != box && reach[nxt] == 0){
  198.                 reach[nxt] =  1;
  199.                 q.pb(nxt);
  200.             }
  201.         }
  202.     }
  203. }
  204. int main(){
  205.    // io("pushabox");
  206.     cin >>n >>m >> q;
  207.     string temporary;
  208.     getline(cin, temporary);
  209.     int cow = 0;
  210.     int box = 0;
  211.     //read input
  212.     f0r(i, n){
  213.         string line;
  214.         getline(cin, line);
  215.         f0r(j, m){
  216.             if(line[j] == '#'){
  217.                 grid[i][j] = 1;
  218.             }
  219.             if(line[j] == 'A'){
  220.                 cow = i*m +j;
  221.             }
  222.             if(line[j] == 'B'){
  223.                 box = i*m+j;
  224.             }
  225.         }
  226.     }
  227.     //find the biconnected components
  228.     b.init(n*m);
  229.     b.bcc();
  230.     //finds where the cow can be around the box
  231.     bfs1(cow, box);
  232.     f0r(i, 4){
  233.         int nxtCow = valid(box, i);
  234.         if(nxtCow != -1 && reach[nxtCow] == 1){
  235.             //bfs from each location to figure which places you can visit
  236.             bfs(nxtCow, box, (i+2)%4);
  237.         }
  238.     }
  239.     f0r(i, q){
  240.         int r, c;
  241.         cin >> r >> c;
  242.         r--; c--;
  243.         int loc = r*m + c;
  244.         if(vis[loc][0] == 1 || vis[loc][1] == 1 || vis[loc][2] == 1 || vis[loc][3] == 1 || loc == box){
  245.             cout << "YES" << endl;
  246.         }
  247.         else{
  248.             cout << "NO" << endl;
  249.         }
  250.     }
  251.     return 0;
  252. }
  253.  
Runtime error #stdin #stdout 0s 68032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SU9VU8
language:
C++ (gcc 8.3)
created:
6 years 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!