제출 #78352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78352		xiaowuc1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	226 ms	76136 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];
set<int> amts[30001];
int src, dest;
int n;

vector<pii> edges[30001];

void solve() {
  priority_queue<pii> q;
  q.push(pii(0, src));
  while(!q.empty()) {
    pii curr = q.top();
    q.pop();
    if(curr.second == dest) {
      printf("%d\n", dp[curr.second]);
      return;
    }
    if(dp[curr.second] != -curr.first) continue;
    for(pii out: edges[curr.second]) {
      int nd = out.first;
      int nw = dp[curr.second] + out.second;
      if(nw < dp[nd]) {
        dp[nd] = nw;
        q.push(pii(-dp[nd], nd));
      }
    }
  }
  printf("-1\n");
}

void loadGraph() {
  for(int i = 0; i < n; i++) {
    for(int out: amts[i]) {
      for(int dx = 1; i - dx * out >= 0; dx++) {
        edges[i].push_back(pii(i-dx*out, dx));
        if(amts[i-dx*out].count(out)) break;
      }
      for(int dx = 1; i + dx * out < n; dx++) {
        edges[i].push_back(pii(i+dx*out, dx));
        if(amts[i+dx*out].count(out)) break;
      }
    }
  }
}

int main() {
  int m;
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) {
    dp[i] = 1 << 25;
  }
  for(int i = 0; i < m; i++) {
    int loc, jump;
    scanf("%d %d", &loc, &jump);
    amts[loc].insert(jump);
    if(i == 0) {
      src = loc;
      dp[loc] = 0;
    }
    else if(i == 1) {
      dest = loc;
    }
  }
  loadGraph();
  solve();
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:75: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: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43