Submission #230517

#	Time	Username	Problem	Language	Result	Execution time	Memory
230517		AlexLuchianov	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1091 ms	34688 KiB

skyscraper

#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 (stderr)

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: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43