제출 #537385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537385		OrazB	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1085 ms	2468 KiB

skyscraper

#include <vector>
#include <list>
#include <map>
#include <set>

#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>

#define FORN(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP(X,Y,Z) for (int (X) = (Y);(X) < (Z);++(X))

#define SZ(Z) ((int)(Z).size())
#define ALL(W) (W).begin(), (W).end()
#define PB push_back

#define MP make_pair
#define A first
#define B second

#define INF 1023123123
#define EPS 1e-11

#define MX(Z,Y) Z = max((Z),(Y))
#define MN(X,Y) X = min((X),(Y))

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vint;

const int kMaxDoge2 = 50005;
vector<int> doges[kMaxDoge2];
int ddone[kMaxDoge2];
int vvalues[kMaxDoge2];

#ifdef DOLPHINIGLE_ENV
int main_c() {
#else
int main() {
#endif
  int n, m;
  scanf("%d %d", &n, &m);
  int initial, target;
  FORN(i, m) {
    int building, power;
    scanf("%d %d", &building, &power);
    doges[building].push_back(power);
    if (!i) initial = building;
    if (i == 1) target = building;
  }
  FORN(i, n) vvalues[i] = -1;
  vvalues[initial] = 0;
  while (true) {
    int best = -1;
    for (int j = 0; j < n; ++j) if (vvalues[j] != -1 && !ddone[j]) {
      if (best == -1 || vvalues[best] > vvalues[j]) best = j;
    }
    if (best == -1) {
      cout << -1 << endl;
      break;
    }
    if (best == target) {
      cout << vvalues[best] << endl;
      break;
    }
    ddone[best] = true;
    for (auto doge: doges[best]) {
      for (int i=0, j = best; j >= 0; j -= doge, ++i) {
        if (vvalues[j] == -1 || vvalues[j] > vvalues[best] + i) {
          vvalues[j] = vvalues[best] + i;
        }
      }
      for (int i=0, j = best; j < n; j += doge, ++i) {
        if (vvalues[j] == -1 || vvalues[j] > vvalues[best] + i) {
          vvalues[j] = vvalues[best] + i;
        }
      }
    }
  }
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:24:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FORN(X,Y) for (int (X) = 0;(X) < (Y);++(X))
      |                            ^
skyscraper.cpp:60:3: note: in expansion of macro 'FORN'
   60 |   FORN(i, m) {
      |   ^~~~
skyscraper.cpp:24:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FORN(X,Y) for (int (X) = 0;(X) < (Y);++(X))
      |                            ^
skyscraper.cpp:67:3: note: in expansion of macro 'FORN'
   67 |   FORN(i, n) vvalues[i] = -1;
      |   ^~~~
skyscraper.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d %d", &building, &power);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:78:5: warning: 'target' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     if (best == target) {
      |     ^~
skyscraper.cpp:68:20: warning: 'initial' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |   vvalues[initial] = 0;
      |   ~~~~~~~~~~~~~~~~~^~~

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