Submission #78351

#	Time	Username	Problem	Language	Result	Execution time	Memory
78351		xiaowuc1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	4 ms	1976 KiB

skyscraper

#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

int dp[30001];
vector<int> edges[30001];
int q[30001];

int main() {
  int m, n;
  scanf("%d%d", &m, &n);
  for(int i = 0; i < m; i++) {
    dp[i] = m+1;
  }
  int ql = 0;
  int qr = 0;
  int dest = -1;
  for(int i = 0; i < n; i++) {
    int loc, jump;
    scanf("%d %d", &loc, &jump);
    edges[loc].push_back(jump);
    if(i == 0) {
      q[qr++] = loc;
      dp[loc] = 0;
    }
    else if(i == 1) {
      dest = loc;
    }
  }
  int ret = m+1;
  while(ql < qr) {
    int curr = q[ql++];
    for(int out: edges[curr]) {
      if(abs(curr-dest)%out == 0) {
        ret = min(ret, dp[curr] + abs(curr-dest) / out);
      }
      if(curr - out >= 0 && dp[curr-out] == m+1) {
        dp[curr-out] = dp[curr]+1;
        q[qr++] = curr-out;
      }
      if(dp[curr-out] == dp[curr] + 1) {
        edges[curr-out].push_back(out);
      }

      if(curr + out >= 0 && dp[curr+out] == m+1) {
        dp[curr+out] = dp[curr]+1;
        q[qr++] = curr+out;
      }
      if(dp[curr+out] == dp[curr] + 1) {
        edges[curr+out].push_back(out);
      }
    }
  }
  if(ret == m+1) ret = -1;
  printf("%d\n", ret);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &m, &n);
   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &loc, &jump);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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