Submission #45937

#	Time	Username	Problem	Language	Result	Execution time	Memory
45937		TheDarkning	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1076 ms	7152 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 = 2e5 + 5;
const int inf = 1e9 + 7;

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

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

inline int readchar()
{
    int c = getchar();
    while ( c <= 32 )
        c = getchar();

    return c;
}

int readInt()
{
    int c = readchar(), x = 0;
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x;
}

main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   scanf("%d%d", &n, &m);

   for( int i = 1; i <= m; i++ )
   {
      p = readInt();
      b = readInt();

      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];

         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; v - i * l > 0; 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("%d", d[x]);
}

Compilation message (stderr)

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

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