fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6. #define ii pair <int, int>
  7. #define fi first
  8. #define se second
  9.  
  10. using namespace std;
  11.  
  12. const int N = 15e3 + 5;
  13. int n, type, m;
  14. ii S, T;
  15. vector <ii> dif[6];
  16.  
  17. struct meteor {
  18.     int x, y, r, t;
  19.     void input() {cin >> x >> y >> r >> t;}
  20. } Meteor[N];
  21.  
  22. void nhap() {
  23.     cin >> type >> n >> m;
  24.     FOR(i, 1, m) Meteor[i].input();
  25.     cin >> S.fi >> S.se >> T.fi >> T.se;
  26.  
  27.     FOR(k, 0, 5) FOR(x, -k, k) FOR(y, -k, k) {
  28.         if (abs(x) + abs(y) <= k) dif[k].push_back({x, y});
  29.     }
  30. }
  31.  
  32. namespace sub1 {
  33.     int mark[505][505], cnt, ans;
  34.     void solve() {
  35.         cnt = ans = 0;
  36.         FOR(t, 0, 59) {
  37.             FOR(i, 1, m) {
  38.                 int d = (Meteor[i].t + t) % Meteor[i].r;
  39.                 if (t) {
  40.                     int last = (d - 1 + Meteor[i].r) % Meteor[i].r;
  41.                     for (auto [dx, dy] : dif[last]) {
  42.                         ii pos = {Meteor[i].x + dx, Meteor[i].y + dy};
  43.                         if (pos.fi < 1 || pos.fi > n || pos.se < 1 || pos.se > n) continue;
  44.                         if (--mark[pos.fi][pos.se] == 0) --cnt;
  45.                     }
  46.                 }
  47.  
  48.                 for (auto [dx, dy] : dif[d]) {
  49.                     ii pos = {Meteor[i].x + dx, Meteor[i].y + dy};
  50.                     if (pos.fi < 1 || pos.fi > n || pos.se < 1 || pos.se > n) continue;
  51.                     if (++mark[pos.fi][pos.se] == 1) ++cnt;
  52.                 }
  53.             }
  54.             ans = max(ans, cnt);
  55.         }
  56.  
  57.         cout << ans;
  58.     }
  59. }
  60.  
  61. namespace sub2 {
  62.     bool mark[505][505][60];
  63.     int dist[505][505][60];
  64.     int dx[] = {0, -1, 0, 1, 0};
  65.     int dy[] = {1, 0, -1, 0, 0};
  66.     const int INF = 1e9;
  67.  
  68.     void solve() {
  69.         if (S == T) {
  70.             cout << 0;
  71.             return ;
  72.         }
  73.  
  74.         FOR(t, 0, 59) FOR(i, 1, m) {
  75.             int d = (Meteor[i].t + t) % Meteor[i].r;
  76.             for (auto [dx_, dy_] : dif[d]) {
  77.                 ii pos = {Meteor[i].x + dx_, Meteor[i].y + dy_};
  78.                 if (pos.fi < 1 || pos.fi > n || pos.se < 1 || pos.se > n) continue;
  79.                 mark[pos.fi][pos.se][t] = 1;
  80.             }
  81.         }
  82.  
  83.         FOR(i, 1, n) FOR(j, 1, n) FOR(t, 0, 59) dist[i][j][t] = INF;
  84.  
  85.         queue<tuple<int,int,int>> q;
  86.         q.push({S.fi, S.se, 0});
  87.         dist[S.fi][S.se][0] = 0;
  88.  
  89.         while (!q.empty()) {
  90.             auto [x, y, t] = q.front(); q.pop();
  91.  
  92.             FOR(i, 0, 4) {
  93.                 int xn = x + dx[i];
  94.                 int yn = y + dy[i];
  95.                 int tn = (t + 1) % 60;
  96.                 if (xn < 1 || xn > n || yn < 1 || yn > n) continue;
  97.                 if (mark[xn][yn][tn]) continue;
  98.                 if (dist[xn][yn][tn] != INF) continue;
  99.                 dist[xn][yn][tn] = dist[x][y][t] + 1;
  100.                 q.push({xn, yn, tn});
  101.             }
  102.         }
  103.  
  104.         int ans = INF;
  105.         FOR(i, 0, 59) ans = min(ans, dist[T.fi][T.se][i]);
  106.         cout << ans;
  107.     }
  108. }
  109.  
  110. void giai() {
  111.     if (type == 1) sub1::solve();
  112.     else sub2::solve();
  113. }
  114.  
  115. int main() {
  116.     ios_base::sync_with_stdio(0);
  117.     cin.tie(0); cout.tie(0);
  118.  
  119.     #define name "test"
  120.  
  121.     if (fopen(name".inp", "r")) {
  122.         freopen(name".inp", "r", stdin);
  123.         freopen(name".out", "w", stdout);
  124.     }
  125.  
  126.     nhap();
  127.     giai();
  128.  
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9kk6uQ
language:
C++14 (clang 8.0)
created:
16 hours 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!