oj.uz

Submission #28046

# Submission time Handle Problem Language Result Execution time Memory
28046 2017-07-15T03:05:31 Z sampriti Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 709 ms 262144 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define LIM 150

int B[30000], P[30000];
set<int> A[30000];
vector<pair<pair<short, unsigned char>, unsigned char> > G[30000][LIM + 1];
int D[30000][LIM + 1];
set<pair<int, pair<short, short> > > Q;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);

  int N, M; cin >> N >> M;

  for(int i = 0; i < M; i++) {
    cin >> B[i] >> P[i];
    A[B[i]].insert(P[i]);
  }

  for(int i = 0; i < N; i++) {
    for(int x: A[i]) {
      if(x < LIM) {
        G[i][LIM].push_back({{i, x}, 0});
      }
    }

    for(int x: A[i]) {
      if(x >= LIM) {
        for(int d = 1; i + d * x < N; d++) {
          if(A[i + d * x].size() == 0) continue;
          G[i][LIM].push_back({{i + d * x, LIM}, d});
        }
        for(int d = 1; i - d * x >= 0; d++) {
          if(A[i - d * x].size() == 0) continue;
          G[i][LIM].push_back({{i - d * x, LIM}, d});
        }
      }
    }

    for(int x = 1; x < LIM; x++) {
      G[i][x].push_back({{i, LIM}, 0});

      if(i + x < N) {
        G[i][x].push_back({{i + x, x}, 1});
      }
      if(i - x >= 0) {
        G[i][x].push_back({{i - x, x}, 1});
      }
    }
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j <= LIM; j++) {
      D[i][j] = INT_MAX/2;
    }
  }

  Q.insert({0, {B[0], LIM}}); D[B[0]][LIM] = 0;

  while(!Q.empty()) {
    auto it = *Q.begin(); Q.erase(Q.begin());
    int i = it.second.first, j = it.second.second;

    if(i == B[1] && j == LIM) break;

    for(auto it2: G[i][j]) {
      int i2 = it2.first.first, j2 = it2.first.second, d = it2.second;
      if(D[i][j] + d < D[i2][j2]) {
        if(D[i2][j2] != INT_MAX/2) {
          Q.erase({D[i2][j2], {i2, j2}});
        }
        D[i2][j2] = D[i][j] + d;
        Q.insert({D[i2][j2], {i2, j2}});
      }
    }
  }

  if(D[B[1]][LIM] == INT_MAX/2) {
    cout << -1 << endl;
  }
  else {
    cout << D[B[1]][LIM] << endl;
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 127692 KB Output is correct
2 Correct 29 ms 127692 KB Output is correct
3 Correct 26 ms 127692 KB Output is correct
4 Correct 29 ms 127692 KB Output is correct
5 Correct 29 ms 127692 KB Output is correct
6 Correct 33 ms 127692 KB Output is correct
7 Correct 19 ms 127692 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 127692 KB Output is correct
2 Correct 19 ms 127692 KB Output is correct
3 Correct 29 ms 127692 KB Output is correct
4 Correct 16 ms 127692 KB Output is correct
5 Correct 29 ms 127692 KB Output is correct
6 Correct 46 ms 127692 KB Output is correct
7 Correct 39 ms 127692 KB Output is correct
8 Correct 29 ms 127824 KB Output is correct
9 Correct 36 ms 127956 KB Output is correct
10 Correct 16 ms 128220 KB Output is correct
11 Correct 23 ms 128220 KB Output is correct
12 Correct 33 ms 128088 KB Output is correct
13 Correct 29 ms 128088 KB Output is correct
14 Correct 29 ms 128352 KB Output is correct
15 Correct 39 ms 128352 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 127692 KB Output is correct
2 Correct 39 ms 127692 KB Output is correct
3 Correct 26 ms 127692 KB Output is correct
4 Correct 39 ms 127692 KB Output is correct
5 Correct 33 ms 127692 KB Output is correct
6 Correct 36 ms 127692 KB Output is correct
7 Correct 29 ms 127692 KB Output is correct
8 Correct 26 ms 127824 KB Output is correct
9 Correct 23 ms 127956 KB Output is correct
10 Correct 33 ms 128220 KB Output is correct
11 Correct 29 ms 128220 KB Output is correct
12 Correct 29 ms 128088 KB Output is correct
13 Correct 33 ms 128088 KB Output is correct
14 Correct 16 ms 128352 KB Output is correct
15 Correct 29 ms 128352 KB Output is correct
16 Correct 43 ms 128616 KB Output is correct
17 Correct 43 ms 131256 KB Output is correct
18 Correct 69 ms 135876 KB Output is correct
19 Correct 59 ms 137064 KB Output is correct
20 Correct 79 ms 137064 KB Output is correct
21 Correct 46 ms 129540 KB Output is correct
22 Correct 69 ms 136008 KB Output is correct
23 Correct 66 ms 135216 KB Output is correct
24 Correct 73 ms 136668 KB Output is correct
25 Correct 69 ms 137064 KB Output is correct
26 Correct 86 ms 136932 KB Output is correct
27 Correct 76 ms 136932 KB Output is correct
28 Correct 96 ms 137064 KB Output is correct
29 Correct 69 ms 137064 KB Output is correct
30 Correct 86 ms 136932 KB Output is correct
31 Correct 106 ms 137064 KB Output is correct
32 Correct 86 ms 137064 KB Output is correct
33 Correct 106 ms 137196 KB Output is correct
34 Correct 93 ms 137196 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 127692 KB Output is correct
2 Correct 33 ms 127692 KB Output is correct
3 Correct 26 ms 127692 KB Output is correct
4 Correct 29 ms 127692 KB Output is correct
5 Correct 26 ms 127692 KB Output is correct
6 Correct 33 ms 127692 KB Output is correct
7 Correct 29 ms 127692 KB Output is correct
8 Correct 33 ms 127824 KB Output is correct
9 Correct 29 ms 127956 KB Output is correct
10 Correct 36 ms 128220 KB Output is correct
11 Correct 29 ms 128220 KB Output is correct
12 Correct 33 ms 128088 KB Output is correct
13 Correct 29 ms 128088 KB Output is correct
14 Correct 29 ms 128352 KB Output is correct
15 Correct 26 ms 128352 KB Output is correct
16 Correct 33 ms 128616 KB Output is correct
17 Correct 43 ms 131256 KB Output is correct
18 Correct 69 ms 135876 KB Output is correct
19 Correct 69 ms 137064 KB Output is correct
20 Correct 86 ms 137064 KB Output is correct
21 Correct 43 ms 129540 KB Output is correct
22 Correct 76 ms 136008 KB Output is correct
23 Correct 63 ms 135216 KB Output is correct
24 Correct 76 ms 136668 KB Output is correct
25 Correct 59 ms 137064 KB Output is correct
26 Correct 73 ms 136932 KB Output is correct
27 Correct 73 ms 136932 KB Output is correct
28 Correct 89 ms 137064 KB Output is correct
29 Correct 89 ms 137064 KB Output is correct
30 Correct 66 ms 136932 KB Output is correct
31 Correct 86 ms 137064 KB Output is correct
32 Correct 93 ms 137064 KB Output is correct
33 Correct 119 ms 137196 KB Output is correct
34 Correct 79 ms 137196 KB Output is correct
35 Correct 86 ms 136008 KB Output is correct
36 Correct 43 ms 132972 KB Output is correct
37 Correct 76 ms 138384 KB Output is correct
38 Correct 113 ms 138912 KB Output is correct
39 Correct 113 ms 138912 KB Output is correct
40 Correct 103 ms 138912 KB Output is correct
41 Correct 96 ms 138912 KB Output is correct
42 Correct 83 ms 136932 KB Output is correct
43 Correct 89 ms 136932 KB Output is correct
44 Correct 73 ms 137064 KB Output is correct
45 Correct 196 ms 139044 KB Output is correct
46 Correct 116 ms 139044 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 127692 KB Output is correct
2 Correct 19 ms 127692 KB Output is correct
3 Correct 19 ms 127692 KB Output is correct
4 Correct 26 ms 127692 KB Output is correct
5 Correct 26 ms 127692 KB Output is correct
6 Correct 36 ms 127692 KB Output is correct
7 Correct 29 ms 127692 KB Output is correct
8 Correct 23 ms 127824 KB Output is correct
9 Correct 19 ms 127956 KB Output is correct
10 Correct 26 ms 128220 KB Output is correct
11 Correct 29 ms 128220 KB Output is correct
12 Correct 36 ms 128088 KB Output is correct
13 Correct 23 ms 128088 KB Output is correct
14 Correct 23 ms 128352 KB Output is correct
15 Correct 26 ms 128352 KB Output is correct
16 Correct 33 ms 128616 KB Output is correct
17 Correct 39 ms 131256 KB Output is correct
18 Correct 76 ms 135876 KB Output is correct
19 Correct 79 ms 137064 KB Output is correct
20 Correct 69 ms 137064 KB Output is correct
21 Correct 43 ms 129540 KB Output is correct
22 Correct 69 ms 136008 KB Output is correct
23 Correct 83 ms 135216 KB Output is correct
24 Correct 79 ms 136668 KB Output is correct
25 Correct 63 ms 137064 KB Output is correct
26 Correct 79 ms 136932 KB Output is correct
27 Correct 73 ms 136932 KB Output is correct
28 Correct 83 ms 137064 KB Output is correct
29 Correct 99 ms 137064 KB Output is correct
30 Correct 86 ms 136932 KB Output is correct
31 Correct 89 ms 137064 KB Output is correct
32 Correct 56 ms 137064 KB Output is correct
33 Correct 133 ms 137196 KB Output is correct
34 Correct 86 ms 137196 KB Output is correct
35 Correct 96 ms 136008 KB Output is correct
36 Correct 49 ms 132972 KB Output is correct
37 Correct 119 ms 138384 KB Output is correct
38 Correct 103 ms 138912 KB Output is correct
39 Correct 119 ms 138912 KB Output is correct
40 Correct 83 ms 138912 KB Output is correct
41 Correct 116 ms 138912 KB Output is correct
42 Correct 83 ms 136932 KB Output is correct
43 Correct 93 ms 136932 KB Output is correct
44 Correct 96 ms 137064 KB Output is correct
45 Correct 186 ms 139044 KB Output is correct
46 Correct 113 ms 139044 KB Output is correct
47 Correct 379 ms 189336 KB Output is correct
48 Correct 573 ms 237516 KB Output is correct
49 Correct 619 ms 247284 KB Output is correct
50 Correct 709 ms 258636 KB Output is correct
51 Memory limit exceeded 636 ms 262144 KB Memory limit exceeded
52 Halted 0 ms 0 KB -