oj.uz

Submission #243207

# Submission time Handle Problem Language Result Execution time Memory
243207 2020-06-30T14:34:40 Z neihcr7j Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 484 ms 262148 KB 
#include<bits/stdc++.h>

#define oo 1000000000
#define maxm 6000000
#define maxn 30005
#define block 200

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 = 200;

vector < int > L[t + 1];
int sz[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]});

  cout << dijkstra();

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 164856 KB Output is correct
2 Correct 104 ms 164728 KB Output is correct
3 Correct 103 ms 164856 KB Output is correct
4 Correct 101 ms 164856 KB Output is correct
5 Correct 112 ms 164728 KB Output is correct
6 Correct 102 ms 164856 KB Output is correct
7 Correct 112 ms 164728 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 164756 KB Output is correct
2 Correct 117 ms 164720 KB Output is correct
3 Correct 116 ms 164728 KB Output is correct
4 Correct 117 ms 164856 KB Output is correct
5 Correct 103 ms 164732 KB Output is correct
6 Correct 114 ms 164848 KB Output is correct
7 Correct 106 ms 164764 KB Output is correct
8 Correct 102 ms 164984 KB Output is correct
9 Correct 102 ms 165112 KB Output is correct
10 Correct 103 ms 165628 KB Output is correct
11 Correct 110 ms 165500 KB Output is correct
12 Correct 116 ms 165496 KB Output is correct
13 Correct 116 ms 165624 KB Output is correct
14 Correct 107 ms 165496 KB Output is correct
15 Correct 102 ms 165496 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 164728 KB Output is correct
2 Correct 107 ms 164728 KB Output is correct
3 Correct 102 ms 164856 KB Output is correct
4 Correct 112 ms 164728 KB Output is correct
5 Correct 99 ms 164728 KB Output is correct
6 Correct 108 ms 164728 KB Output is correct
7 Correct 103 ms 164856 KB Output is correct
8 Correct 105 ms 164984 KB Output is correct
9 Correct 113 ms 165112 KB Output is correct
10 Correct 108 ms 165496 KB Output is correct
11 Correct 129 ms 165624 KB Output is correct
12 Correct 109 ms 165500 KB Output is correct
13 Correct 114 ms 165496 KB Output is correct
14 Correct 109 ms 165624 KB Output is correct
15 Correct 122 ms 165624 KB Output is correct
16 Correct 108 ms 166136 KB Output is correct
17 Correct 130 ms 171768 KB Output is correct
18 Correct 196 ms 180832 KB Output is correct
19 Correct 206 ms 183416 KB Output is correct
20 Correct 195 ms 183288 KB Output is correct
21 Correct 117 ms 167928 KB Output is correct
22 Correct 175 ms 181244 KB Output is correct
23 Correct 171 ms 180088 KB Output is correct
24 Correct 193 ms 183288 KB Output is correct
25 Correct 198 ms 183416 KB Output is correct
26 Correct 191 ms 183416 KB Output is correct
27 Correct 196 ms 183928 KB Output is correct
28 Correct 209 ms 184280 KB Output is correct
29 Correct 220 ms 183800 KB Output is correct
30 Correct 198 ms 183392 KB Output is correct
31 Correct 223 ms 183748 KB Output is correct
32 Correct 219 ms 183544 KB Output is correct
33 Correct 240 ms 184312 KB Output is correct
34 Correct 225 ms 184184 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 164796 KB Output is correct
2 Correct 114 ms 164728 KB Output is correct
3 Correct 115 ms 164728 KB Output is correct
4 Correct 103 ms 164728 KB Output is correct
5 Correct 121 ms 164836 KB Output is correct
6 Correct 105 ms 164728 KB Output is correct
7 Correct 112 ms 164856 KB Output is correct
8 Correct 113 ms 164984 KB Output is correct
9 Correct 111 ms 165112 KB Output is correct
10 Correct 107 ms 165496 KB Output is correct
11 Correct 110 ms 165496 KB Output is correct
12 Correct 105 ms 165496 KB Output is correct
13 Correct 106 ms 165496 KB Output is correct
14 Correct 107 ms 165496 KB Output is correct
15 Correct 107 ms 165624 KB Output is correct
16 Correct 109 ms 166136 KB Output is correct
17 Correct 127 ms 171900 KB Output is correct
18 Correct 181 ms 180872 KB Output is correct
19 Correct 206 ms 183288 KB Output is correct
20 Correct 208 ms 183416 KB Output is correct
21 Correct 129 ms 167928 KB Output is correct
22 Correct 194 ms 181240 KB Output is correct
23 Correct 191 ms 180108 KB Output is correct
24 Correct 193 ms 183416 KB Output is correct
25 Correct 210 ms 183288 KB Output is correct
26 Correct 201 ms 183416 KB Output is correct
27 Correct 215 ms 183928 KB Output is correct
28 Correct 192 ms 184184 KB Output is correct
29 Correct 229 ms 183800 KB Output is correct
30 Correct 223 ms 183416 KB Output is correct
31 Correct 223 ms 183672 KB Output is correct
32 Correct 224 ms 183672 KB Output is correct
33 Correct 232 ms 184440 KB Output is correct
34 Correct 222 ms 184056 KB Output is correct
35 Correct 192 ms 179576 KB Output is correct
36 Correct 151 ms 175040 KB Output is correct
37 Correct 227 ms 185080 KB Output is correct
38 Correct 232 ms 185720 KB Output is correct
39 Correct 225 ms 184188 KB Output is correct
40 Correct 221 ms 184312 KB Output is correct
41 Correct 233 ms 185208 KB Output is correct
42 Correct 230 ms 184052 KB Output is correct
43 Correct 199 ms 184436 KB Output is correct
44 Correct 202 ms 183924 KB Output is correct
45 Correct 297 ms 187896 KB Output is correct
46 Correct 251 ms 187004 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 164984 KB Output is correct
2 Correct 106 ms 164728 KB Output is correct
3 Correct 100 ms 164856 KB Output is correct
4 Correct 101 ms 164728 KB Output is correct
5 Correct 122 ms 164860 KB Output is correct
6 Correct 100 ms 164728 KB Output is correct
7 Correct 105 ms 164856 KB Output is correct
8 Correct 106 ms 164984 KB Output is correct
9 Correct 106 ms 165112 KB Output is correct
10 Correct 111 ms 165496 KB Output is correct
11 Correct 136 ms 165460 KB Output is correct
12 Correct 115 ms 165468 KB Output is correct
13 Correct 108 ms 165496 KB Output is correct
14 Correct 103 ms 165496 KB Output is correct
15 Correct 105 ms 165624 KB Output is correct
16 Correct 110 ms 166136 KB Output is correct
17 Correct 131 ms 171800 KB Output is correct
18 Correct 176 ms 180856 KB Output is correct
19 Correct 200 ms 183288 KB Output is correct
20 Correct 191 ms 183288 KB Output is correct
21 Correct 114 ms 167928 KB Output is correct
22 Correct 189 ms 181276 KB Output is correct
23 Correct 172 ms 180192 KB Output is correct
24 Correct 191 ms 183288 KB Output is correct
25 Correct 206 ms 183536 KB Output is correct
26 Correct 201 ms 183548 KB Output is correct
27 Correct 195 ms 183928 KB Output is correct
28 Correct 198 ms 184160 KB Output is correct
29 Correct 221 ms 183928 KB Output is correct
30 Correct 197 ms 183416 KB Output is correct
31 Correct 248 ms 183672 KB Output is correct
32 Correct 226 ms 183508 KB Output is correct
33 Correct 227 ms 184312 KB Output is correct
34 Correct 243 ms 184056 KB Output is correct
35 Correct 203 ms 179680 KB Output is correct
36 Correct 143 ms 174968 KB Output is correct
37 Correct 208 ms 185080 KB Output is correct
38 Correct 247 ms 185592 KB Output is correct
39 Correct 237 ms 184184 KB Output is correct
40 Correct 217 ms 184440 KB Output is correct
41 Correct 232 ms 185208 KB Output is correct
42 Correct 218 ms 184052 KB Output is correct
43 Correct 207 ms 184436 KB Output is correct
44 Correct 210 ms 183924 KB Output is correct
45 Correct 271 ms 187896 KB Output is correct
46 Correct 248 ms 187000 KB Output is correct
47 Runtime error 484 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -