oj.uz

Submission #230516

# Submission time Handle Problem Language Result Execution time Memory
230516 2020-05-10T09:46:52 Z AlexLuchianov Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 6 ms 1024 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 30000;
int v[1 + nmax][2];
vector<int> g[1 + nmax];
map<pair<int,int>, int> dp;
int seen[1 + nmax];

queue<pair<int,int>> q;

void processlevel(int node, int cost){
  if(seen[node] == 1)
    return ;
  seen[node] = 1;
  for(int h = 0; h < g[node].size(); h++){
    int jump2 = g[node][h];
    if(dp.find({node, jump2}) == dp.end()){
      dp[{node, jump2}] = cost;
      q.push({node, jump2});
    }
  }
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 0;i < m; i++) {
    cin >> v[i][0] >> v[i][1];
    g[v[i][0]].push_back(v[i][1]);
  }
  processlevel(v[0][0], 0);

  while(0 < q.size()){
    int node = q.front().first;
    int jump = q.front().second;
    int cost = dp[{node, jump}];
    q.pop();

    if(0 <= node - jump)
      if(dp.find({node - jump, jump}) == dp.end()) {
        dp[{node - jump, jump}] = cost + 1;
        processlevel(node + jump, cost + 1);
        q.push({node - jump, jump});
      }
    if(node + jump < n)
      if(dp.find({node + jump, jump}) == dp.end()) {
        dp[{node + jump, jump}] = cost + 1;
        processlevel(node + jump, cost + 1);
        q.push({node + jump, jump});
      }
  }

  if(dp.find({v[1][0], v[1][1]}) == dp.end())
    cout << -1;
  else
    cout << dp[{v[1][0], v[1][1]}];
  return 0;
}

Compilation message

skyscraper.cpp: In function 'void processlevel(int, int)':
skyscraper.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Incorrect 5 ms 1024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Incorrect 5 ms 1024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Incorrect 5 ms 1024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Incorrect 5 ms 1024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Incorrect 5 ms 1024 KB Output isn't correct
7 Halted 0 ms 0 KB -