Submission #45928

#	Time	Username	Problem	Language	Result	Execution time	Memory
45928		TheDarkning	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1078 ms	3196 KiB

skyscraper

/**
                  ▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀
                  <⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋>

            ♔♕♖♗♘♙ ☜❷☞✪ ィℋ६ ≈ ᗫẵℜℵĬŊĞ ✪☜❷☞ ♚♛♜♝♞♟
            ♔♕♖♗♘♙                             ♚♛♜♝♞♟
                      ˙·٠•●♥ Ƹ̵̡Ӝ̵̨̄Ʒ ♥●•٠·˙

**/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <map>
#include <deque>
#include <string>
#include <memory.h>
#include <queue>
#include <set>
#include <assert.h>

#define sz(s) s.size()
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 3e4 + 5;
const int inf = 1e9 + 7;

int n, m, p, b, x, s, cnt;
int d[N];
vector < int > w[N];
priority_queue < pair < int, int > > q;

main()
{
   scanf("%d%d", &n, &m);

   for( int i = 1; i <= m; i++ )
   {
      scanf("%d%d", &p, &b);
      p++;

      if( i == 1 )
         s = p;
      if( i == 2 )
         x = p;

      w[ p ].pb( b );
   }
   for (int i = 1; i <= n; i ++) {
      sort (w[i].begin(),w[i].end());
      w[i].erase(unique(w[i].begin(),w[i].end()),w[i].end());
   }
   for (int i = 1; i <= n; i ++)
      d[i] = inf;

   d[ s ] = 0;

   q.push( mk( d[s], s ) );

   while( !q.empty() )
   {
      int v = q.top().sc, cur = -q.top().fr;
      q.pop();

      if( cur > d[ v ] ) continue;

      if (v == x) {
         printf("%d", d[v]);
         return 0;
      }
      for(int j = 0; j < w[v].size(); j ++)
      {
         int l = w[v][j];
         int to = v;
         cnt = 0;

         while( to <= n )
         {
            cnt++;
            to = v + l * cnt;
            if( to > n )  break;
            if( d[ v ] + cnt < d[ to ] )
            {
               d[ to ] = d[ v ] + cnt;
               q.push( mk( -d[ to ], to ) );
            }
         }

         to = v;
         cnt = 0;

         while( to )
         {
            cnt++;
            to = v - l * cnt;
            if( to <= 0 ) break;
            if( d[ v ] + cnt < d[ to ] )
            {
               d[ to ] = d[ v ] + cnt;
               q.push( mk( -d[ to ], to ) );
            }
         }
      }
   }
   if( d[ x ] == inf )
      d[ x ] = -1;
   printf("%d", d[x]);
}

Compilation message (stderr)

skyscraper.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:80:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < w[v].size(); j ++)
                      ~~^~~~~~~~~~~~~
skyscraper.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:48:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &p, &b);
       ~~~~~^~~~~~~~~~~~~~~~

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