oj.uz

Submission #28035

# Submission time Handle Problem Language Result Execution time Memory
28035 2017-07-15T00:36:58 Z sampriti Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 70448 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define LIM 50

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 13 ms 45500 KB Output is correct
2 Correct 9 ms 45500 KB Output is correct
3 Correct 13 ms 45500 KB Output is correct
4 Correct 16 ms 45500 KB Output is correct
5 Correct 9 ms 45500 KB Output is correct
6 Correct 9 ms 45500 KB Output is correct
7 Correct 16 ms 45500 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 45500 KB Output is correct
2 Correct 9 ms 45500 KB Output is correct
3 Correct 13 ms 45500 KB Output is correct
4 Correct 3 ms 45500 KB Output is correct
5 Correct 9 ms 45500 KB Output is correct
6 Correct 16 ms 45500 KB Output is correct
7 Correct 3 ms 45500 KB Output is correct
8 Correct 9 ms 45632 KB Output is correct
9 Correct 13 ms 45632 KB Output is correct
10 Correct 13 ms 45764 KB Output is correct
11 Correct 16 ms 45764 KB Output is correct
12 Correct 6 ms 45632 KB Output is correct
13 Correct 6 ms 45632 KB Output is correct
14 Correct 9 ms 45896 KB Output is correct
15 Correct 16 ms 45896 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45500 KB Output is correct
2 Correct 9 ms 45500 KB Output is correct
3 Correct 9 ms 45500 KB Output is correct
4 Correct 13 ms 45500 KB Output is correct
5 Correct 3 ms 45500 KB Output is correct
6 Correct 13 ms 45500 KB Output is correct
7 Correct 13 ms 45500 KB Output is correct
8 Correct 6 ms 45632 KB Output is correct
9 Correct 9 ms 45632 KB Output is correct
10 Correct 6 ms 45764 KB Output is correct
11 Correct 9 ms 45764 KB Output is correct
12 Correct 6 ms 45632 KB Output is correct
13 Correct 13 ms 45632 KB Output is correct
14 Correct 13 ms 45896 KB Output is correct
15 Correct 13 ms 45896 KB Output is correct
16 Correct 16 ms 45896 KB Output is correct
17 Correct 23 ms 46820 KB Output is correct
18 Correct 26 ms 48272 KB Output is correct
19 Correct 26 ms 48668 KB Output is correct
20 Correct 43 ms 48800 KB Output is correct
21 Correct 13 ms 46160 KB Output is correct
22 Correct 36 ms 48272 KB Output is correct
23 Correct 33 ms 48008 KB Output is correct
24 Correct 33 ms 48668 KB Output is correct
25 Correct 33 ms 48668 KB Output is correct
26 Correct 29 ms 48668 KB Output is correct
27 Correct 33 ms 48668 KB Output is correct
28 Correct 26 ms 48800 KB Output is correct
29 Correct 49 ms 48668 KB Output is correct
30 Correct 33 ms 48536 KB Output is correct
31 Correct 43 ms 48668 KB Output is correct
32 Correct 26 ms 48668 KB Output is correct
33 Correct 59 ms 49196 KB Output is correct
34 Correct 59 ms 49196 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45500 KB Output is correct
2 Correct 6 ms 45500 KB Output is correct
3 Correct 6 ms 45500 KB Output is correct
4 Correct 9 ms 45500 KB Output is correct
5 Correct 16 ms 45500 KB Output is correct
6 Correct 13 ms 45500 KB Output is correct
7 Correct 3 ms 45500 KB Output is correct
8 Correct 9 ms 45632 KB Output is correct
9 Correct 16 ms 45632 KB Output is correct
10 Correct 9 ms 45764 KB Output is correct
11 Correct 13 ms 45764 KB Output is correct
12 Correct 9 ms 45632 KB Output is correct
13 Correct 9 ms 45632 KB Output is correct
14 Correct 9 ms 45896 KB Output is correct
15 Correct 9 ms 45896 KB Output is correct
16 Correct 9 ms 45896 KB Output is correct
17 Correct 16 ms 46820 KB Output is correct
18 Correct 33 ms 48272 KB Output is correct
19 Correct 26 ms 48668 KB Output is correct
20 Correct 26 ms 48800 KB Output is correct
21 Correct 6 ms 46160 KB Output is correct
22 Correct 19 ms 48272 KB Output is correct
23 Correct 16 ms 48008 KB Output is correct
24 Correct 23 ms 48668 KB Output is correct
25 Correct 36 ms 48668 KB Output is correct
26 Correct 26 ms 48668 KB Output is correct
27 Correct 26 ms 48668 KB Output is correct
28 Correct 36 ms 48800 KB Output is correct
29 Correct 46 ms 48668 KB Output is correct
30 Correct 26 ms 48536 KB Output is correct
31 Correct 36 ms 48668 KB Output is correct
32 Correct 43 ms 48668 KB Output is correct
33 Correct 56 ms 49196 KB Output is correct
34 Correct 56 ms 49196 KB Output is correct
35 Correct 73 ms 49460 KB Output is correct
36 Correct 33 ms 47480 KB Output is correct
37 Correct 86 ms 50384 KB Output is correct
38 Correct 93 ms 50912 KB Output is correct
39 Correct 83 ms 50780 KB Output is correct
40 Correct 93 ms 50912 KB Output is correct
41 Correct 99 ms 50912 KB Output is correct
42 Correct 43 ms 48668 KB Output is correct
43 Correct 39 ms 48668 KB Output is correct
44 Correct 46 ms 48800 KB Output is correct
45 Correct 83 ms 53116 KB Output is correct
46 Correct 96 ms 53116 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45500 KB Output is correct
2 Correct 9 ms 45500 KB Output is correct
3 Correct 13 ms 45500 KB Output is correct
4 Correct 19 ms 45500 KB Output is correct
5 Correct 9 ms 45500 KB Output is correct
6 Correct 6 ms 45500 KB Output is correct
7 Correct 13 ms 45500 KB Output is correct
8 Correct 9 ms 45632 KB Output is correct
9 Correct 9 ms 45632 KB Output is correct
10 Correct 16 ms 45764 KB Output is correct
11 Correct 19 ms 45764 KB Output is correct
12 Correct 9 ms 45632 KB Output is correct
13 Correct 6 ms 45632 KB Output is correct
14 Correct 16 ms 45896 KB Output is correct
15 Correct 9 ms 45896 KB Output is correct
16 Correct 13 ms 45896 KB Output is correct
17 Correct 16 ms 46820 KB Output is correct
18 Correct 19 ms 48272 KB Output is correct
19 Correct 23 ms 48668 KB Output is correct
20 Correct 36 ms 48800 KB Output is correct
21 Correct 16 ms 46160 KB Output is correct
22 Correct 26 ms 48272 KB Output is correct
23 Correct 29 ms 48008 KB Output is correct
24 Correct 29 ms 48668 KB Output is correct
25 Correct 39 ms 48668 KB Output is correct
26 Correct 26 ms 48668 KB Output is correct
27 Correct 29 ms 48668 KB Output is correct
28 Correct 36 ms 48800 KB Output is correct
29 Correct 49 ms 48668 KB Output is correct
30 Correct 43 ms 48536 KB Output is correct
31 Correct 43 ms 48668 KB Output is correct
32 Correct 26 ms 48668 KB Output is correct
33 Correct 59 ms 49196 KB Output is correct
34 Correct 56 ms 49196 KB Output is correct
35 Correct 59 ms 49460 KB Output is correct
36 Correct 19 ms 47480 KB Output is correct
37 Correct 59 ms 50384 KB Output is correct
38 Correct 83 ms 50912 KB Output is correct
39 Correct 86 ms 50780 KB Output is correct
40 Correct 76 ms 50912 KB Output is correct
41 Correct 96 ms 50912 KB Output is correct
42 Correct 43 ms 48668 KB Output is correct
43 Correct 49 ms 48668 KB Output is correct
44 Correct 46 ms 48800 KB Output is correct
45 Correct 106 ms 53116 KB Output is correct
46 Correct 86 ms 53116 KB Output is correct
47 Execution timed out 1000 ms 70448 KB Execution timed out
48 Halted 0 ms 0 KB -