Submission #230518

#	Time	Username	Problem	Language	Result	Execution time	Memory
230518		AlexLuchianov	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1088 ms	88044 KiB

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_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];

unordered_map<int, int> dp[1 + nmax];

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[node][jump2] == 0){
      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], 1);

  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[node - jump][jump] == 0) {
        dp[node - jump][jump] = cost + 1;
        processlevel(node - jump, cost + 1);
        q.push({node - jump, jump});
      }
    if(node + jump < n)
      if(dp[node + jump][jump] == 0) {
        dp[node + jump][jump] = cost + 1;
        processlevel(node + jump, cost + 1);
        q.push({node + jump, jump});
      }
  }

  cout << dp[v[1][0]][v[1][1]] - 1;
  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43