vlatkovski

usaco replication third fail

Apr 11th, 2021
468
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int dr[4] = {-1, 0, 1, 0};
  5. const int dc[4] = {0, 1, 0, -1};
  6.  
  7. const int MAXN = 1010;
  8.  
  9. int n, D;
  10.  
  11. bool wall[MAXN][MAXN];
  12. int dist[MAXN][MAXN];
  13. int firstiter[MAXN][MAXN];
  14. bool vis[MAXN][MAXN][2];
  15. bool vis2[MAXN][MAXN];
  16. vector<pair<int, int>> queues[MAXN];
  17.  
  18. //vector<vector<bool>> wall, vis2;
  19. //vector<vector<int>> dist, firstiter;
  20. //vector<vector<pair<int, int>>> queues;
  21.  
  22. int main() {
  23.     cin.tie(0)->sync_with_stdio(false);
  24. //  #ifndef _DEBUG
  25. //  freopen("dream.in", "r", stdin);
  26. //  freopen("dream.out", "w", stdout);
  27. //  #endif
  28. //  wall.assign(MAXN, vector<bool>(MAXN));
  29. //  dist.assign(MAXN, vector<int>(MAXN));
  30. //  firstiter.assign(MAXN, vector<int>(MAXN));
  31. //  vis2.assign(MAXN, vector<bool>(MAXN));
  32. //  queues.assign(MAXN, vector<pair<int, int>>());
  33.     cin >> n >> D;
  34.     queue<pair<int, int>> q;
  35.     queue<tuple<int, int, int>> q2;
  36.     for (int r = 1; r <= n; ++r) {
  37.         for (int c = 1; c <= n; ++c) {
  38.             dist[r][c] = -1;
  39.             vis[r][c][0] = vis[r][c][1] = false;
  40.             firstiter[r][c] = -1;
  41.             char ch;
  42.             cin >> ch;
  43.             if (ch == 'S') {
  44.                 ch = '.';
  45.                 q2.emplace(r, c, 0);
  46.                 vis[r][c][0] = true;
  47.             }
  48.             if (ch == '.') {
  49.                 wall[r][c] = false;
  50.             } else {
  51.                 wall[r][c] = true;
  52.                 q.emplace(r, c);
  53.                 dist[r][c] = 0;
  54.             }
  55.         }
  56.     }
  57.     while (!q.empty()) {
  58.         int r, c;
  59.         tie(r, c) = q.front();
  60.         q.pop();
  61.         for (int dir = 0; dir < 4; ++dir) {
  62.             int r1 = r + dr[dir];
  63.             int c1 = c + dc[dir];
  64.             if (dist[r1][c1] == -1) {
  65.                 dist[r1][c1] = dist[r][c] + 1;
  66.                 q.emplace(r1, c1);
  67.             }
  68.         }
  69.     }
  70.     while (!q2.empty()) {
  71.         int r, c, t;
  72.         tie(r, c, t) = q2.front();
  73.         q2.pop();
  74.         int par = t % 2;
  75.         int iter = t / D;
  76.         firstiter[r][c] = iter;
  77.         if (t > 0 && t % D == 0) {
  78.             // expand
  79.             if (iter >= dist[r][c]) {
  80.                 // no space
  81.                 firstiter[r][c] = iter-1; // before expanding
  82.                 continue;
  83.             }
  84.         }
  85.         for (int dir = 0; dir < 4; ++dir) {
  86.             int r1 = r + dr[dir];
  87.             int c1 = c + dc[dir];
  88.             if (wall[r1][c1] || vis[r1][c1][1-par]) continue;
  89.             if (iter >= dist[r1][c1]) continue;
  90.             vis[r1][c1][1-par] = true;
  91.             q2.emplace(r1, c1, t+1);
  92.         }
  93.     }
  94. //  static int PAPA[MAXN][MAXN];
  95.     int dpar = D % 2;
  96.     for (int r = 1; r <= n; ++r) {
  97.         for (int c = 1; c <= n; ++c) {
  98.             vis2[r][c] = false;
  99.             int maxiter = -1;
  100.             if (vis[r][c][dpar]) {
  101.                 maxiter = max(maxiter, firstiter[r][c]);
  102.                 int x = dist[r][c]-1;
  103.                 for (int dir = 0; dir < 4; ++dir) {
  104.                     int r1 = r + dc[dir];
  105.                     int c1 = c + dc[dir];
  106.                     if (!vis[r1][c1][1-dpar]) continue;
  107.                     int x1 = dist[r1][c1]-1;
  108.                     maxiter = max(maxiter, min(x, x1+1));
  109.                 }
  110.             }
  111.             if (vis[r][c][1-dpar]) {
  112.                 maxiter = max(maxiter, firstiter[r][c]);
  113.                 for (int dir = 0; dir < 4; ++dir) {
  114.                     int r1 = r + dc[dir];
  115.                     int c1 = c + dc[dir];
  116.                     if (!vis[r1][c1][dpar]) continue;
  117.                     int x1 = dist[r1][c1]-1;
  118.                     maxiter = max(maxiter, x1);
  119.                 }
  120.             }
  121.             if (maxiter >= 0) {
  122.                 queues[maxiter].emplace_back(r, c);
  123.             }
  124. //          PAPA[r][c]=maxiter;
  125.         }
  126.     }
  127.     int ans = 0;
  128.     for (int iter = n; iter >= 0; --iter) {
  129.         for (auto& cell : queues[iter]) {
  130.             int r, c;
  131.             tie(r, c) = cell;
  132.             if (vis2[r][c]) continue;
  133.             vis2[r][c] = true;
  134.             ++ans; // #vis2
  135.             if (iter == 0) continue;
  136.             for (int dir = 0; dir < 4; ++dir) {
  137.                 int r1 = r + dr[dir];
  138.                 int c1 = c + dc[dir];
  139.                 if (!wall[r1][c1] && !vis2[r1][c1]) {
  140.                     queues[iter-1].emplace_back(r1, c1);
  141.                 }
  142.             }
  143.         }
  144.     }
  145.     cout << ans << '\n';
  146. //  cout<<"vis:\n";
  147. //  for (int r = 1; r <= n; ++r) {
  148. //      for (int c = 1; c <= n ; ++c) {
  149. //          if (wall[r][c]) cout<<"#";
  150. //          else if (vis2[r][c]) cout << "x";
  151. //          else cout << ".";
  152. //      }
  153. //      cout<<"\n";
  154. //  }
  155. //  cout<<"dist:\n";
  156. //  for (int r = 1; r <= n; ++r) {
  157. //      for (int c = 1; c <= n; ++c) {
  158. //          cout<<dist[r][c];
  159. //      }
  160. //      cout<<"\n";
  161. //  }
  162. //  cout<<"visparity:\n";
  163. //  for (int r = 1; r <= n; ++r) {
  164. //      for (int c = 1; c <= n; ++c) {
  165. //          if(wall[r][c])cout<<"#";
  166. //          else if (vis[r][c][0]&&vis[r][c][1])cout<<"2";
  167. //          else if (vis[r][c][0])cout<<"0";
  168. //          else if (vis[r][c][1])cout<<"1";
  169. //          else cout<<".";;
  170. //      }
  171. //      cout<<"\n";
  172. //  }
  173. //  cout<<"maxiter:\n";
  174. //  for (int r = 1; r <= n; ++r) {
  175. //      for (int c = 1; c <= n; ++c) {
  176. //          if(wall[r][c])cout<<"#";
  177. //          else if (PAPA[r][c]==-1) cout << ".";
  178. //          else cout<<PAPA[r][c];
  179. //      }
  180. //      cout<<"\n";
  181. //  }
  182. //  cout<<"firstiter:\n";
  183. //  for (int r = 1; r <= n; ++r) {
  184. //      for (int c = 1; c <= n; ++c) {
  185. //          if(wall[r][c])cout<<"#";
  186. //          else if (firstiter[r][c]==-1) cout << ".";
  187. //          else cout<<firstiter[r][c];
  188. //      }
  189. //      cout<<"\n";
  190. //  }
  191. }
  192.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×