oj.uz

Submission #28031

# Submission time Handle Problem Language Result Execution time Memory
28031 2017-07-15T00:33:10 Z sampriti Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 109 ms 262144 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define LIM 300

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 56 ms 250576 KB Output is correct
2 Correct 59 ms 250576 KB Output is correct
3 Correct 56 ms 250708 KB Output is correct
4 Correct 73 ms 250708 KB Output is correct
5 Correct 63 ms 250708 KB Output is correct
6 Correct 63 ms 250708 KB Output is correct
7 Correct 46 ms 250708 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 250576 KB Output is correct
2 Correct 46 ms 250576 KB Output is correct
3 Correct 56 ms 250708 KB Output is correct
4 Correct 53 ms 250708 KB Output is correct
5 Correct 66 ms 250708 KB Output is correct
6 Correct 43 ms 250708 KB Output is correct
7 Correct 59 ms 250708 KB Output is correct
8 Correct 46 ms 250972 KB Output is correct
9 Correct 53 ms 251104 KB Output is correct
10 Correct 56 ms 251500 KB Output is correct
11 Correct 36 ms 251632 KB Output is correct
12 Correct 66 ms 251500 KB Output is correct
13 Correct 53 ms 251500 KB Output is correct
14 Correct 69 ms 251764 KB Output is correct
15 Correct 73 ms 251764 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 250576 KB Output is correct
2 Correct 46 ms 250576 KB Output is correct
3 Correct 66 ms 250708 KB Output is correct
4 Correct 56 ms 250708 KB Output is correct
5 Correct 36 ms 250708 KB Output is correct
6 Correct 56 ms 250708 KB Output is correct
7 Correct 49 ms 250708 KB Output is correct
8 Correct 63 ms 250972 KB Output is correct
9 Correct 63 ms 251104 KB Output is correct
10 Correct 53 ms 251500 KB Output is correct
11 Correct 56 ms 251632 KB Output is correct
12 Correct 56 ms 251500 KB Output is correct
13 Correct 49 ms 251500 KB Output is correct
14 Correct 66 ms 251764 KB Output is correct
15 Correct 63 ms 251764 KB Output is correct
16 Correct 69 ms 252556 KB Output is correct
17 Correct 109 ms 257704 KB Output is correct
18 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 250576 KB Output is correct
2 Correct 69 ms 250576 KB Output is correct
3 Correct 49 ms 250708 KB Output is correct
4 Correct 59 ms 250708 KB Output is correct
5 Correct 59 ms 250708 KB Output is correct
6 Correct 56 ms 250708 KB Output is correct
7 Correct 53 ms 250708 KB Output is correct
8 Correct 56 ms 250972 KB Output is correct
9 Correct 46 ms 251104 KB Output is correct
10 Correct 59 ms 251500 KB Output is correct
11 Correct 69 ms 251632 KB Output is correct
12 Correct 53 ms 251500 KB Output is correct
13 Correct 49 ms 251500 KB Output is correct
14 Correct 63 ms 251764 KB Output is correct
15 Correct 56 ms 251764 KB Output is correct
16 Correct 46 ms 252556 KB Output is correct
17 Correct 96 ms 257704 KB Output is correct
18 Memory limit exceeded 83 ms 262144 KB Memory limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 250576 KB Output is correct
2 Correct 53 ms 250576 KB Output is correct
3 Correct 49 ms 250708 KB Output is correct
4 Correct 56 ms 250708 KB Output is correct
5 Correct 46 ms 250708 KB Output is correct
6 Correct 53 ms 250708 KB Output is correct
7 Correct 49 ms 250708 KB Output is correct
8 Correct 53 ms 250972 KB Output is correct
9 Correct 66 ms 251104 KB Output is correct
10 Correct 59 ms 251500 KB Output is correct
11 Correct 53 ms 251632 KB Output is correct
12 Correct 56 ms 251500 KB Output is correct
13 Correct 53 ms 251500 KB Output is correct
14 Correct 39 ms 251764 KB Output is correct
15 Correct 53 ms 251764 KB Output is correct
16 Correct 56 ms 252556 KB Output is correct
17 Correct 99 ms 257704 KB Output is correct
18 Memory limit exceeded 69 ms 262144 KB Memory limit exceeded
19 Halted 0 ms 0 KB -