oj.uz

Submission #28032

# Submission time Handle Problem Language Result Execution time Memory
28032 2017-07-15T00:34:01 Z sampriti Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 813 ms 262144 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define LIM 200

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

int main() {
  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++) {
          G[i][LIM].push_back({{i + d * x, LIM}, d});
        }
        for(int d = 1; i - d * x >= 0; d++) {
          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;
    }
  }

  set<pair<int, pair<int, int> > > Q;
  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;

    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 36 ms 168548 KB Output is correct
2 Correct 43 ms 168548 KB Output is correct
3 Correct 39 ms 168548 KB Output is correct
4 Correct 36 ms 168548 KB Output is correct
5 Correct 29 ms 168680 KB Output is correct
6 Correct 36 ms 168680 KB Output is correct
7 Correct 39 ms 168680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 168548 KB Output is correct
2 Correct 36 ms 168548 KB Output is correct
3 Correct 36 ms 168548 KB Output is correct
4 Correct 53 ms 168548 KB Output is correct
5 Correct 49 ms 168680 KB Output is correct
6 Correct 29 ms 168680 KB Output is correct
7 Correct 43 ms 168680 KB Output is correct
8 Correct 49 ms 168812 KB Output is correct
9 Correct 23 ms 168944 KB Output is correct
10 Correct 36 ms 169208 KB Output is correct
11 Correct 36 ms 169340 KB Output is correct
12 Correct 49 ms 169208 KB Output is correct
13 Correct 33 ms 169208 KB Output is correct
14 Correct 29 ms 169472 KB Output is correct
15 Correct 43 ms 169472 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 168548 KB Output is correct
2 Correct 46 ms 168548 KB Output is correct
3 Correct 36 ms 168548 KB Output is correct
4 Correct 39 ms 168548 KB Output is correct
5 Correct 29 ms 168680 KB Output is correct
6 Correct 29 ms 168680 KB Output is correct
7 Correct 46 ms 168680 KB Output is correct
8 Correct 43 ms 168812 KB Output is correct
9 Correct 33 ms 168944 KB Output is correct
10 Correct 43 ms 169208 KB Output is correct
11 Correct 33 ms 169340 KB Output is correct
12 Correct 49 ms 169208 KB Output is correct
13 Correct 53 ms 169208 KB Output is correct
14 Correct 33 ms 169472 KB Output is correct
15 Correct 33 ms 169472 KB Output is correct
16 Correct 33 ms 169868 KB Output is correct
17 Correct 69 ms 173300 KB Output is correct
18 Correct 76 ms 179504 KB Output is correct
19 Correct 109 ms 181088 KB Output is correct
20 Correct 89 ms 181220 KB Output is correct
21 Correct 46 ms 171056 KB Output is correct
22 Correct 116 ms 179636 KB Output is correct
23 Correct 83 ms 178580 KB Output is correct
24 Correct 143 ms 180560 KB Output is correct
25 Correct 113 ms 181088 KB Output is correct
26 Correct 103 ms 180956 KB Output is correct
27 Correct 106 ms 180956 KB Output is correct
28 Correct 96 ms 181088 KB Output is correct
29 Correct 109 ms 181088 KB Output is correct
30 Correct 123 ms 180956 KB Output is correct
31 Correct 113 ms 181088 KB Output is correct
32 Correct 116 ms 181088 KB Output is correct
33 Correct 156 ms 181220 KB Output is correct
34 Correct 143 ms 181220 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 168548 KB Output is correct
2 Correct 29 ms 168548 KB Output is correct
3 Correct 36 ms 168548 KB Output is correct
4 Correct 36 ms 168548 KB Output is correct
5 Correct 39 ms 168680 KB Output is correct
6 Correct 33 ms 168680 KB Output is correct
7 Correct 33 ms 168680 KB Output is correct
8 Correct 33 ms 168812 KB Output is correct
9 Correct 36 ms 168944 KB Output is correct
10 Correct 39 ms 169208 KB Output is correct
11 Correct 39 ms 169340 KB Output is correct
12 Correct 29 ms 169208 KB Output is correct
13 Correct 43 ms 169208 KB Output is correct
14 Correct 46 ms 169472 KB Output is correct
15 Correct 36 ms 169472 KB Output is correct
16 Correct 36 ms 169868 KB Output is correct
17 Correct 76 ms 173300 KB Output is correct
18 Correct 96 ms 179504 KB Output is correct
19 Correct 89 ms 181088 KB Output is correct
20 Correct 93 ms 181220 KB Output is correct
21 Correct 46 ms 171056 KB Output is correct
22 Correct 76 ms 179636 KB Output is correct
23 Correct 76 ms 178580 KB Output is correct
24 Correct 89 ms 180560 KB Output is correct
25 Correct 99 ms 181088 KB Output is correct
26 Correct 113 ms 180956 KB Output is correct
27 Correct 79 ms 180956 KB Output is correct
28 Correct 113 ms 181088 KB Output is correct
29 Correct 123 ms 181088 KB Output is correct
30 Correct 93 ms 180956 KB Output is correct
31 Correct 113 ms 181088 KB Output is correct
32 Correct 99 ms 181088 KB Output is correct
33 Correct 136 ms 181220 KB Output is correct
34 Correct 159 ms 181220 KB Output is correct
35 Correct 139 ms 179240 KB Output is correct
36 Correct 86 ms 175676 KB Output is correct
37 Correct 166 ms 182408 KB Output is correct
38 Correct 163 ms 183200 KB Output is correct
39 Correct 169 ms 183200 KB Output is correct
40 Correct 186 ms 183200 KB Output is correct
41 Correct 186 ms 183200 KB Output is correct
42 Correct 109 ms 180956 KB Output is correct
43 Correct 106 ms 180956 KB Output is correct
44 Correct 103 ms 181220 KB Output is correct
45 Correct 293 ms 184660 KB Output is correct
46 Correct 256 ms 184660 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 168548 KB Output is correct
2 Correct 33 ms 168548 KB Output is correct
3 Correct 36 ms 168548 KB Output is correct
4 Correct 39 ms 168548 KB Output is correct
5 Correct 26 ms 168680 KB Output is correct
6 Correct 36 ms 168680 KB Output is correct
7 Correct 29 ms 168680 KB Output is correct
8 Correct 33 ms 168812 KB Output is correct
9 Correct 43 ms 168944 KB Output is correct
10 Correct 49 ms 169208 KB Output is correct
11 Correct 49 ms 169340 KB Output is correct
12 Correct 43 ms 169208 KB Output is correct
13 Correct 46 ms 169208 KB Output is correct
14 Correct 33 ms 169472 KB Output is correct
15 Correct 29 ms 169472 KB Output is correct
16 Correct 43 ms 169868 KB Output is correct
17 Correct 63 ms 173300 KB Output is correct
18 Correct 96 ms 179504 KB Output is correct
19 Correct 89 ms 181088 KB Output is correct
20 Correct 93 ms 181220 KB Output is correct
21 Correct 49 ms 171056 KB Output is correct
22 Correct 89 ms 179636 KB Output is correct
23 Correct 103 ms 178580 KB Output is correct
24 Correct 119 ms 180560 KB Output is correct
25 Correct 79 ms 181088 KB Output is correct
26 Correct 99 ms 180956 KB Output is correct
27 Correct 113 ms 180956 KB Output is correct
28 Correct 103 ms 181088 KB Output is correct
29 Correct 139 ms 181088 KB Output is correct
30 Correct 89 ms 180956 KB Output is correct
31 Correct 116 ms 181088 KB Output is correct
32 Correct 103 ms 181088 KB Output is correct
33 Correct 153 ms 181220 KB Output is correct
34 Correct 126 ms 181220 KB Output is correct
35 Correct 156 ms 179240 KB Output is correct
36 Correct 73 ms 175676 KB Output is correct
37 Correct 176 ms 182408 KB Output is correct
38 Correct 173 ms 183200 KB Output is correct
39 Correct 183 ms 183200 KB Output is correct
40 Correct 183 ms 183200 KB Output is correct
41 Correct 173 ms 183200 KB Output is correct
42 Correct 119 ms 180956 KB Output is correct
43 Correct 109 ms 180956 KB Output is correct
44 Correct 113 ms 181220 KB Output is correct
45 Correct 256 ms 184660 KB Output is correct
46 Correct 276 ms 184660 KB Output is correct
47 Correct 813 ms 249860 KB Output is correct
48 Memory limit exceeded 453 ms 262144 KB Memory limit exceeded
49 Halted 0 ms 0 KB -