oj.uz

Submission #245531

# Submission time Handle Problem Language Result Execution time Memory
245531 2020-07-06T16:17:16 Z kevlee Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
 822 ms 147440 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define flush fflush(stdout)
#define debug printf("Hello\n")
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int n, m, k, x, y, sum, cnt, ans = inf, b[30005], po[30005];
int d[30005][175];
vi v[30005];
const int SQ = 173;
struct state {
  int dist, pos, power; //for buildings: power = 0
  bool operator <(const state& rhs) const {
    return dist > rhs.dist;
  }
};
vector <pii> edges[30005][175]; //(position, power)
int main () {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  scanf("%d %d", &n, &m);
  FOR(i, 1, m) {
    scanf("%d %d", &b[i], &po[i]);
    v[b[i]].pb(po[i]);
  }
  FOR(i, 0, n-1) {
    sort(all(v[i]));
    auto it = unique(v[i].begin(), v[i].end());
    v[i].resize(distance(v[i].begin(), it));
    FOR(j, 0, 174) {
      d[i][j] = inf;
    }
  }
  d[b[1]][0] = 0;
  priority_queue <state> pq;
  pq.push((state){0, b[1], 0});
  while (!pq.empty()) {
    state cur = pq.top();
    pq.pop();
    if (d[cur.pos][cur.power] != cur.dist) continue;
    if (cur.pos == b[2]) {
      ans = min(ans, cur.dist);
      continue;
    }
    if (cur.power == 0) {
      for (auto p: v[cur.pos]) {
        if (p >= SQ) {
          for (int j = cur.pos - p, cost = 1; j >= 0; j -= p, cost++) {
            if (cur.dist + cost < d[j][0]) {
              d[j][0] = cur.dist + cost;
              pq.push((state){d[j][0], j, 0});
            }
          }
          for (int j = cur.pos + p, cost = 1; j < n; j += p, cost++) {
            if (cur.dist + cost < d[j][0]) {
              d[j][0] = cur.dist + cost;
              pq.push((state){d[j][0], j, 0});
            }
          }
        } else {
          if (cur.dist < d[cur.pos][p]) {
            d[cur.pos][p] = cur.dist;
            pq.push((state){d[cur.pos][p], cur.pos, p}); 
          }
        }
      }
    } else {
      if (cur.dist < d[cur.pos][0]) {
        d[cur.pos][0] = cur.dist;
        pq.push((state){d[cur.pos][0], cur.pos, 0});
      }
      if (cur.pos + cur.power < n && cur.dist + 1 < d[cur.pos + cur.power][cur.power]) {
        d[cur.pos + cur.power][cur.power] = cur.dist + 1;
        pq.push((state){d[cur.pos + cur.power][cur.power], cur.pos + cur.power, cur.power});
      }
      if (cur.pos - cur.power >= 0 && cur.dist + 1 < d[cur.pos - cur.power][cur.power]) {
        d[cur.pos - cur.power][cur.power] = cur.dist + 1;
        pq.push((state){d[cur.pos - cur.power][cur.power], cur.pos - cur.power, cur.power});
      }
    }
  }
  if (ans == inf) printf("-1\n");
  else printf("%d\n", ans);
  return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &b[i], &po[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 124408 KB Output is correct
2 Correct 88 ms 124408 KB Output is correct
3 Correct 79 ms 124408 KB Output is correct
4 Correct 77 ms 124420 KB Output is correct
5 Correct 90 ms 124408 KB Output is correct
6 Correct 93 ms 124408 KB Output is correct
7 Correct 78 ms 124408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 124408 KB Output is correct
2 Correct 92 ms 124340 KB Output is correct
3 Correct 91 ms 124408 KB Output is correct
4 Correct 78 ms 124408 KB Output is correct
5 Correct 86 ms 124568 KB Output is correct
6 Correct 78 ms 124408 KB Output is correct
7 Correct 87 ms 124408 KB Output is correct
8 Correct 90 ms 124412 KB Output is correct
9 Correct 82 ms 124408 KB Output is correct
10 Correct 87 ms 124536 KB Output is correct
11 Correct 78 ms 124536 KB Output is correct
12 Correct 79 ms 124536 KB Output is correct
13 Correct 91 ms 124540 KB Output is correct
14 Correct 78 ms 124480 KB Output is correct
15 Correct 91 ms 124536 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 124408 KB Output is correct
2 Correct 81 ms 124408 KB Output is correct
3 Correct 78 ms 124316 KB Output is correct
4 Correct 79 ms 124408 KB Output is correct
5 Correct 86 ms 124520 KB Output is correct
6 Correct 76 ms 124408 KB Output is correct
7 Correct 82 ms 124408 KB Output is correct
8 Correct 81 ms 124412 KB Output is correct
9 Correct 82 ms 124408 KB Output is correct
10 Correct 80 ms 124408 KB Output is correct
11 Correct 83 ms 124536 KB Output is correct
12 Correct 100 ms 124424 KB Output is correct
13 Correct 80 ms 124536 KB Output is correct
14 Correct 80 ms 124536 KB Output is correct
15 Correct 83 ms 124536 KB Output is correct
16 Correct 79 ms 124536 KB Output is correct
17 Correct 79 ms 124920 KB Output is correct
18 Correct 78 ms 125560 KB Output is correct
19 Correct 83 ms 125816 KB Output is correct
20 Correct 80 ms 125816 KB Output is correct
21 Correct 99 ms 124664 KB Output is correct
22 Correct 93 ms 125560 KB Output is correct
23 Correct 83 ms 125560 KB Output is correct
24 Correct 94 ms 125688 KB Output is correct
25 Correct 97 ms 125816 KB Output is correct
26 Correct 78 ms 125816 KB Output is correct
27 Correct 79 ms 125944 KB Output is correct
28 Correct 81 ms 125816 KB Output is correct
29 Correct 82 ms 125740 KB Output is correct
30 Correct 79 ms 125688 KB Output is correct
31 Correct 82 ms 125816 KB Output is correct
32 Correct 80 ms 125816 KB Output is correct
33 Correct 89 ms 125944 KB Output is correct
34 Correct 102 ms 125816 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 124408 KB Output is correct
2 Correct 92 ms 124412 KB Output is correct
3 Correct 78 ms 124408 KB Output is correct
4 Correct 78 ms 124412 KB Output is correct
5 Correct 78 ms 124408 KB Output is correct
6 Correct 78 ms 124416 KB Output is correct
7 Correct 79 ms 124408 KB Output is correct
8 Correct 77 ms 124408 KB Output is correct
9 Correct 80 ms 124536 KB Output is correct
10 Correct 79 ms 124408 KB Output is correct
11 Correct 84 ms 124464 KB Output is correct
12 Correct 79 ms 124408 KB Output is correct
13 Correct 87 ms 124540 KB Output is correct
14 Correct 95 ms 124680 KB Output is correct
15 Correct 80 ms 124536 KB Output is correct
16 Correct 81 ms 124536 KB Output is correct
17 Correct 83 ms 124920 KB Output is correct
18 Correct 80 ms 125556 KB Output is correct
19 Correct 80 ms 125864 KB Output is correct
20 Correct 79 ms 125944 KB Output is correct
21 Correct 80 ms 124668 KB Output is correct
22 Correct 81 ms 125560 KB Output is correct
23 Correct 81 ms 125448 KB Output is correct
24 Correct 79 ms 125688 KB Output is correct
25 Correct 81 ms 125816 KB Output is correct
26 Correct 78 ms 125816 KB Output is correct
27 Correct 83 ms 125816 KB Output is correct
28 Correct 81 ms 125816 KB Output is correct
29 Correct 83 ms 125816 KB Output is correct
30 Correct 82 ms 125688 KB Output is correct
31 Correct 82 ms 125816 KB Output is correct
32 Correct 80 ms 125816 KB Output is correct
33 Correct 87 ms 125816 KB Output is correct
34 Correct 88 ms 125816 KB Output is correct
35 Correct 93 ms 126072 KB Output is correct
36 Correct 81 ms 125308 KB Output is correct
37 Correct 95 ms 126328 KB Output is correct
38 Correct 105 ms 126680 KB Output is correct
39 Correct 108 ms 126584 KB Output is correct
40 Correct 111 ms 126584 KB Output is correct
41 Correct 114 ms 126584 KB Output is correct
42 Correct 87 ms 126456 KB Output is correct
43 Correct 99 ms 126456 KB Output is correct
44 Correct 90 ms 126412 KB Output is correct
45 Correct 133 ms 126908 KB Output is correct
46 Correct 113 ms 126952 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 124408 KB Output is correct
2 Correct 78 ms 124328 KB Output is correct
3 Correct 81 ms 124408 KB Output is correct
4 Correct 85 ms 124408 KB Output is correct
5 Correct 94 ms 124408 KB Output is correct
6 Correct 78 ms 124408 KB Output is correct
7 Correct 78 ms 124384 KB Output is correct
8 Correct 78 ms 124408 KB Output is correct
9 Correct 90 ms 124408 KB Output is correct
10 Correct 78 ms 124408 KB Output is correct
11 Correct 79 ms 124536 KB Output is correct
12 Correct 78 ms 124408 KB Output is correct
13 Correct 92 ms 124408 KB Output is correct
14 Correct 78 ms 124536 KB Output is correct
15 Correct 90 ms 124536 KB Output is correct
16 Correct 80 ms 124536 KB Output is correct
17 Correct 80 ms 124920 KB Output is correct
18 Correct 80 ms 125560 KB Output is correct
19 Correct 86 ms 125688 KB Output is correct
20 Correct 92 ms 125816 KB Output is correct
21 Correct 80 ms 124664 KB Output is correct
22 Correct 82 ms 125792 KB Output is correct
23 Correct 81 ms 125560 KB Output is correct
24 Correct 79 ms 125688 KB Output is correct
25 Correct 80 ms 125816 KB Output is correct
26 Correct 80 ms 125820 KB Output is correct
27 Correct 81 ms 125944 KB Output is correct
28 Correct 80 ms 125816 KB Output is correct
29 Correct 98 ms 125816 KB Output is correct
30 Correct 83 ms 125688 KB Output is correct
31 Correct 83 ms 125816 KB Output is correct
32 Correct 94 ms 125688 KB Output is correct
33 Correct 86 ms 125816 KB Output is correct
34 Correct 88 ms 125816 KB Output is correct
35 Correct 91 ms 126200 KB Output is correct
36 Correct 81 ms 125304 KB Output is correct
37 Correct 108 ms 126380 KB Output is correct
38 Correct 95 ms 126584 KB Output is correct
39 Correct 102 ms 126628 KB Output is correct
40 Correct 110 ms 126584 KB Output is correct
41 Correct 99 ms 126584 KB Output is correct
42 Correct 86 ms 126456 KB Output is correct
43 Correct 85 ms 126456 KB Output is correct
44 Correct 100 ms 126412 KB Output is correct
45 Correct 125 ms 126908 KB Output is correct
46 Correct 115 ms 126904 KB Output is correct
47 Correct 155 ms 134200 KB Output is correct
48 Correct 100 ms 141176 KB Output is correct
49 Correct 99 ms 142584 KB Output is correct
50 Correct 95 ms 144120 KB Output is correct
51 Correct 148 ms 146616 KB Output is correct
52 Correct 141 ms 146616 KB Output is correct
53 Correct 104 ms 146040 KB Output is correct
54 Correct 94 ms 144888 KB Output is correct
55 Correct 94 ms 144888 KB Output is correct
56 Correct 104 ms 146296 KB Output is correct
57 Correct 186 ms 145016 KB Output is correct
58 Correct 98 ms 145528 KB Output is correct
59 Correct 116 ms 145632 KB Output is correct
60 Correct 114 ms 145656 KB Output is correct
61 Correct 119 ms 145656 KB Output is correct
62 Correct 128 ms 146424 KB Output is correct
63 Correct 154 ms 147440 KB Output is correct
64 Correct 148 ms 147264 KB Output is correct
65 Correct 329 ms 147312 KB Output is correct
66 Correct 822 ms 147192 KB Output is correct
67 Correct 750 ms 147184 KB Output is correct