oj.uz

Submission #45935

# Submission time Handle Problem Language Result Execution time Memory
45935 2018-04-16T13:57:16 Z TheDarkning Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1000 ms 5372 KB 
/**
                  ▄█▀ ▀█▀ ▄▀▄ █▀ █▄█▄█ ▄▀▄ █▀ ▄█▀
                  <⇋⇋⇋⋛∰≓⊂(⌒,_ゝ⌒)⊃≓∰⋛⇋⇋⇋>

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

**/

#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;
int d[N];

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

   for( int i = 1; i <= m; i++ )
   {
      char e, o;
      e = getchar();
      while( e == '\n' or e == ' ' )
         e = getchar();
      o = getchar();
      while( o == '\n' or o == ' ' )
         o = getchar();

      p = e - 48;
      b = o - 48;

      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 )
      puts("-1");
   else
      printf("%d", d[x]);
}

Compilation message

skyscraper.cpp:43:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < w[v].size(); j ++)
                      ~~^~~~~~~~~~~~~
skyscraper.cpp:45: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 5096 KB Output is correct
3 Correct 6 ms 5164 KB Output is correct
4 Correct 5 ms 5216 KB Output is correct
5 Correct 6 ms 5216 KB Output is correct
6 Correct 5 ms 5216 KB Output is correct
7 Correct 6 ms 5216 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5216 KB Output is correct
2 Correct 6 ms 5216 KB Output is correct
3 Correct 6 ms 5216 KB Output is correct
4 Correct 6 ms 5220 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 7 ms 5248 KB Output is correct
7 Correct 6 ms 5296 KB Output is correct
8 Execution timed out 1082 ms 5296 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5296 KB Output is correct
2 Correct 6 ms 5296 KB Output is correct
3 Correct 5 ms 5296 KB Output is correct
4 Correct 5 ms 5296 KB Output is correct
5 Correct 6 ms 5296 KB Output is correct
6 Correct 5 ms 5296 KB Output is correct
7 Correct 5 ms 5296 KB Output is correct
8 Execution timed out 1081 ms 5296 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5296 KB Output is correct
2 Correct 7 ms 5296 KB Output is correct
3 Correct 6 ms 5296 KB Output is correct
4 Correct 7 ms 5296 KB Output is correct
5 Correct 5 ms 5296 KB Output is correct
6 Correct 6 ms 5372 KB Output is correct
7 Correct 5 ms 5372 KB Output is correct
8 Execution timed out 1067 ms 5372 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5372 KB Output is correct
2 Correct 7 ms 5372 KB Output is correct
3 Correct 5 ms 5372 KB Output is correct
4 Correct 6 ms 5372 KB Output is correct
5 Correct 6 ms 5372 KB Output is correct
6 Correct 5 ms 5372 KB Output is correct
7 Correct 6 ms 5372 KB Output is correct
8 Execution timed out 1081 ms 5372 KB Time limit exceeded
9 Halted 0 ms 0 KB -