oj.uz

Submission #243203

# Submission time Handle Problem Language Result Execution time Memory
243203 2020-06-30T14:31:55 Z neihcr7j Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 231724 KB 
#include<bits/stdc++.h>

#define oo 1000000000
#define maxm 4000000
#define maxn 30005
#define block 100

using namespace std;
typedef long long ll;

int n, m;
int b[maxn], p[maxn];

vector < pair < int, int > > g[maxm];

int node(int u, int x) {return x * n + u;}

int dist[maxm], vis[maxm];

const int t = 300;

vector < int > L[t + 1];

int dijkstra() {
  fill(dist, dist + maxm, oo);
  dist[b[0]] = 0;
  L[0].push_back(b[0]);

  int M = maxn - 1;

  for (int i = 0; i <= M; ++i)
    while (!L[i % t].empty()) {
      int u = L[i % t].back(); L[i % t].pop_back();

      if (u == b[1])
        return i;

      if (dist[u] < i || vis[u]) continue;
      vis[u] = 1;

      for (auto x : g[u]) {
        int v = x.first, w = x.second;
        if (dist[v] > dist[u] + w) {
          dist[v] = dist[u] + w;
          L[dist[v] % t].push_back(v);
        }
      }
    }

  return (dist[b[1]] == oo ? -1 : dist[b[1]]);
}

int main(){

  #define TASK "ABC"
//	freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 0; i < m; ++i)
    cin >> b[i] >> p[i];

  for (int j = 1; j <= block; ++j)
    for (int i = j; i < n; ++i)
      g[node(i, j)].push_back({node(i - j, j), 1});

  for (int j = 1; j <= block; ++j)
    for (int i = 0; i + j < n; ++i)
      g[node(i, j)].push_back({node(i + j, j), 1});

  for (int i = 0; i < n; ++i)
    for (int j = 1; j <= block; ++j)
      g[node(i, j)].push_back({i, 0});

  for (int i = 0; i < m; ++i)
    if (p[i] <= block)
      g[b[i]].push_back({node(b[i], p[i]), 0});


  for (int i = 0; i < m; ++i)
    if (p[i] > block)
      for (int j = b[i] % p[i]; j < n; j += p[i])
        if (b[i] != j)
          g[b[i]].push_back({j, abs(j - b[i]) / p[i]});

  //for (int i = 0; i < 10; ++i)
   // for (auto j : g[i])
   //   cerr << i << ' ' << j.first << ' ' << j.second << '\n';
  cout << dijkstra();

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 109944 KB Output is correct
2 Correct 71 ms 109944 KB Output is correct
3 Correct 71 ms 109944 KB Output is correct
4 Correct 71 ms 109944 KB Output is correct
5 Correct 69 ms 109944 KB Output is correct
6 Correct 71 ms 109948 KB Output is correct
7 Correct 73 ms 109944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 109948 KB Output is correct
2 Correct 71 ms 109944 KB Output is correct
3 Correct 79 ms 109948 KB Output is correct
4 Correct 73 ms 109944 KB Output is correct
5 Correct 75 ms 109944 KB Output is correct
6 Correct 70 ms 109944 KB Output is correct
7 Correct 70 ms 109944 KB Output is correct
8 Correct 70 ms 110072 KB Output is correct
9 Correct 76 ms 110200 KB Output is correct
10 Correct 74 ms 110328 KB Output is correct
11 Correct 82 ms 110376 KB Output is correct
12 Correct 72 ms 110328 KB Output is correct
13 Correct 79 ms 110328 KB Output is correct
14 Correct 73 ms 110332 KB Output is correct
15 Correct 75 ms 110584 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 109980 KB Output is correct
2 Correct 72 ms 109944 KB Output is correct
3 Correct 77 ms 109944 KB Output is correct
4 Correct 75 ms 109944 KB Output is correct
5 Correct 71 ms 109944 KB Output is correct
6 Correct 70 ms 109944 KB Output is correct
7 Correct 69 ms 109944 KB Output is correct
8 Correct 79 ms 110072 KB Output is correct
9 Correct 71 ms 110200 KB Output is correct
10 Correct 74 ms 110400 KB Output is correct
11 Correct 74 ms 110352 KB Output is correct
12 Correct 73 ms 110328 KB Output is correct
13 Correct 71 ms 110328 KB Output is correct
14 Correct 72 ms 110328 KB Output is correct
15 Correct 71 ms 110328 KB Output is correct
16 Correct 73 ms 110840 KB Output is correct
17 Correct 88 ms 113656 KB Output is correct
18 Correct 117 ms 118136 KB Output is correct
19 Correct 112 ms 119288 KB Output is correct
20 Correct 112 ms 119544 KB Output is correct
21 Correct 78 ms 111736 KB Output is correct
22 Correct 108 ms 118264 KB Output is correct
23 Correct 106 ms 117752 KB Output is correct
24 Correct 119 ms 119416 KB Output is correct
25 Correct 116 ms 119496 KB Output is correct
26 Correct 120 ms 119416 KB Output is correct
27 Correct 124 ms 119672 KB Output is correct
28 Correct 123 ms 119960 KB Output is correct
29 Correct 127 ms 119940 KB Output is correct
30 Correct 127 ms 119416 KB Output is correct
31 Correct 129 ms 119656 KB Output is correct
32 Correct 122 ms 119672 KB Output is correct
33 Correct 139 ms 120312 KB Output is correct
34 Correct 130 ms 120056 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 109944 KB Output is correct
2 Correct 97 ms 109944 KB Output is correct
3 Correct 79 ms 109944 KB Output is correct
4 Correct 71 ms 109944 KB Output is correct
5 Correct 74 ms 109944 KB Output is correct
6 Correct 84 ms 109944 KB Output is correct
7 Correct 75 ms 110048 KB Output is correct
8 Correct 79 ms 110108 KB Output is correct
9 Correct 71 ms 110204 KB Output is correct
10 Correct 77 ms 110328 KB Output is correct
11 Correct 76 ms 110456 KB Output is correct
12 Correct 73 ms 110508 KB Output is correct
13 Correct 76 ms 110328 KB Output is correct
14 Correct 79 ms 110328 KB Output is correct
15 Correct 87 ms 110464 KB Output is correct
16 Correct 79 ms 110796 KB Output is correct
17 Correct 88 ms 113744 KB Output is correct
18 Correct 117 ms 118136 KB Output is correct
19 Correct 121 ms 119288 KB Output is correct
20 Correct 126 ms 119416 KB Output is correct
21 Correct 83 ms 111736 KB Output is correct
22 Correct 130 ms 118384 KB Output is correct
23 Correct 114 ms 117752 KB Output is correct
24 Correct 124 ms 119356 KB Output is correct
25 Correct 117 ms 119288 KB Output is correct
26 Correct 118 ms 119420 KB Output is correct
27 Correct 146 ms 119676 KB Output is correct
28 Correct 130 ms 119928 KB Output is correct
29 Correct 138 ms 119928 KB Output is correct
30 Correct 117 ms 119548 KB Output is correct
31 Correct 117 ms 119676 KB Output is correct
32 Correct 119 ms 119544 KB Output is correct
33 Correct 128 ms 120312 KB Output is correct
34 Correct 120 ms 120056 KB Output is correct
35 Correct 112 ms 118136 KB Output is correct
36 Correct 98 ms 115320 KB Output is correct
37 Correct 125 ms 121080 KB Output is correct
38 Correct 130 ms 121464 KB Output is correct
39 Correct 126 ms 120568 KB Output is correct
40 Correct 126 ms 120696 KB Output is correct
41 Correct 133 ms 121208 KB Output is correct
42 Correct 126 ms 120180 KB Output is correct
43 Correct 124 ms 120564 KB Output is correct
44 Correct 119 ms 120180 KB Output is correct
45 Correct 151 ms 124024 KB Output is correct
46 Correct 136 ms 123512 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 109920 KB Output is correct
2 Correct 70 ms 109944 KB Output is correct
3 Correct 76 ms 109944 KB Output is correct
4 Correct 72 ms 109944 KB Output is correct
5 Correct 72 ms 109944 KB Output is correct
6 Correct 72 ms 109944 KB Output is correct
7 Correct 73 ms 109944 KB Output is correct
8 Correct 72 ms 110072 KB Output is correct
9 Correct 75 ms 110292 KB Output is correct
10 Correct 76 ms 110456 KB Output is correct
11 Correct 72 ms 110328 KB Output is correct
12 Correct 72 ms 110328 KB Output is correct
13 Correct 78 ms 110328 KB Output is correct
14 Correct 75 ms 110584 KB Output is correct
15 Correct 73 ms 110456 KB Output is correct
16 Correct 75 ms 110840 KB Output is correct
17 Correct 87 ms 113656 KB Output is correct
18 Correct 106 ms 118136 KB Output is correct
19 Correct 116 ms 119368 KB Output is correct
20 Correct 112 ms 119416 KB Output is correct
21 Correct 77 ms 111736 KB Output is correct
22 Correct 109 ms 118264 KB Output is correct
23 Correct 105 ms 117756 KB Output is correct
24 Correct 117 ms 119416 KB Output is correct
25 Correct 116 ms 119288 KB Output is correct
26 Correct 121 ms 119416 KB Output is correct
27 Correct 119 ms 119672 KB Output is correct
28 Correct 117 ms 119928 KB Output is correct
29 Correct 122 ms 119800 KB Output is correct
30 Correct 116 ms 119416 KB Output is correct
31 Correct 124 ms 119672 KB Output is correct
32 Correct 118 ms 119544 KB Output is correct
33 Correct 137 ms 120508 KB Output is correct
34 Correct 130 ms 120072 KB Output is correct
35 Correct 123 ms 118136 KB Output is correct
36 Correct 95 ms 115320 KB Output is correct
37 Correct 124 ms 121080 KB Output is correct
38 Correct 127 ms 121336 KB Output is correct
39 Correct 128 ms 120696 KB Output is correct
40 Correct 128 ms 120636 KB Output is correct
41 Correct 141 ms 121208 KB Output is correct
42 Correct 124 ms 120208 KB Output is correct
43 Correct 119 ms 120436 KB Output is correct
44 Correct 132 ms 120160 KB Output is correct
45 Correct 160 ms 124024 KB Output is correct
46 Correct 135 ms 123412 KB Output is correct
47 Correct 528 ms 174396 KB Output is correct
48 Correct 994 ms 221764 KB Output is correct
49 Execution timed out 1100 ms 231724 KB Time limit exceeded
50 Halted 0 ms 0 KB -