Submission #196996

#	Time	Username	Problem	Language	Result	Execution time	Memory
196996		quocnguyen1012	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	6 ms	1272 KiB

skyscraper

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 3e4 + 5;

int N, M;
vector<int> have[maxn];
int dist[maxn], b[maxn], p[maxn];

bool Have(int pos, int val)
{
  int l = lower_bound(have[pos].begin(), have[pos].end(), val) - have[pos].begin();
  return (l < have[pos].size() && have[pos][l] == val);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  cin >> N >> M;
  for (int i = 0; i < M; ++i){
    cin >> b[i] >> p[i];
    have[b[i]].pb(p[i]);
  }
  pq.push(mp(b[0], 0));
  fill_n(&dist[0], maxn, 1e9 + 5);
  dist[b[0]] = 0;
  for (int i = 0; i < N; ++i){
    sort(have[i].begin(), have[i].end());
    have[i].erase(unique(have[i].begin(), have[i].end()), have[i].end());
  }
  while (pq.size()){
    auto now = pq.top(); pq.pop();
    if (dist[now.se] != now.fi) continue;
    //cerr << now.fi << ' ' << now.se << '\n';
    for (auto all : have[now.se]){
      for (int i = 1; i < maxn; ++i){
        if (now.se + i * all < N){
          if (dist[now.se + i * all] > now.fi + i){
            dist[now.se + i * all] = now.fi + i;
            pq.push(mp(now.fi + i, now.se + i * all));
            if (Have(now.se + i * all, all)) break;
          }
        }
        else break;
      }
      for (int i = 1; i < maxn; ++i){
        if (now.se - i * all >= 0){
          if (dist[now.se - i * all] > now.fi + i){
            dist[now.se - i * all] = now.fi + i;
            pq.push(mp(now.fi + i, now.se - i * all));
            if (Have(now.se - i * all, all)) break;
          }
        }
        else break;
      }
    }
  }
  if (dist[b[1]] == 1e9 + 5) dist[b[1]] = -1;
  cout << dist[b[1]] << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'bool Have(int, int)':
skyscraper.cpp:20:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   return (l < have[pos].size() && have[pos][l] == val);
           ~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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