Submission #45948

#	Time	Username	Problem	Language	Result	Execution time	Memory
45948		TheDarkning	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	990 ms	10212 KiB

skyscraper

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

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

**/

#include <bits/stdc++.h>

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

using namespace std;

const int N = 2e5 + 5;
const int inf = 1e15 + 7;

vector < int > w[N];
priority_queue < pair < int, int > > q;

int n, m, p, b, x, s, cnt, to;
int d[N];

main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   scanf("%lld%lld", &n, &m);

   for( int i = 1; i <= m; i++ )
   {
      scanf("%lld%lld", &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("%lld", d[v]);
         return 0;
      }
      for( auto l : w[v] )
      {
         for( int i = 1; i * l + v <= n; i++ )
         {
            to = v + l * i;
            if( d[ v ] + i < d[ to ] )
            {
               d[ to ] = d[ v ] + i;
               q.push( mk( -d[ to ], to ) );
            }
         }
         for( int i = 1; i * l <= v; i++ )
         {
            to = v - l * i;

            if( d[ v ] + i < d[ to ] )
            {
               d[ to ] = d[ v ] + i;
               q.push( mk( -d[ to ], to ) );
            }
         }
      }
   }
   if( d[ x ] == inf )
      puts("-1");
   else
      printf("%lld", d[x]);
}

Compilation message (stderr)

skyscraper.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:42:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld%lld", &p, &b);
       ~~~~~^~~~~~~~~~~~~~~~~~~~

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