oj.uz

Submission #28030

# Submission time Handle Problem Language Result Execution time Memory
28030 2017-07-15T00:32:07 Z sampriti Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 0 ms 1848 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define LIM 500

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -