Submission #208572

#	Time	Username	Problem	Language	Result	Execution time	Memory
208572		DodgeBallMan	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	253 ms	64748 KiB

skyscraper

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 3e4 + 10;
const int M = 2e3 + 5;
int n, m, d[N], st, en, inf = 1e9;
bool chk[N][M];
vector<int> g[N];
priority_queue<pii, vector<pii>, greater<pii>> q;

int main()
{
    fill( d, d+N, inf );
    scanf("%d %d",&n,&m);
    for( int i = 0, a, b ; i < m ; i++ ) {
        scanf("%d %d",&a,&b);
        g[a].emplace_back( b );
        if( i == 0 ) st = a;
        else if( i == 1 ) en = a;
    }
    for( int i = 0 ; i < n ; i++ ) {
        sort( g[i].begin(), g[i].end() );
        g[i].resize(unique(g[i].begin(), g[i].end())-g[i].begin());
    } 
    q.emplace( d[st] = 0, st );
    while( !q.empty() ) {
        pii now = q.top(); q.pop();
        if( d[now.y] != now.x ) continue;
        for( int p : g[now.y] ) {
            for( int i = now.y + p, cnt = 1 ; i < n ; i += p, cnt++ ) {
                if( p < M && chk[i][p] ) break ;
                if( d[i] > d[now.y] + cnt ) {
                    q.emplace( d[i] = d[now.y] + cnt, i );
                    if( p < M ) chk[i][p] = true;
                }
            }
            for( int i = now.y - p, cnt = 1 ; i >= 0 ; i -= p, cnt++ ) {
                if( p < M && chk[i][p] ) break ;
                if( d[i] > d[now.y] + cnt ) {
                    q.emplace( d[i] = d[now.y] + cnt, i );
                    if( p < M ) chk[i][p] = true;
                }
            }
        }
    }
    printf("%d",d[en]==inf?-1:d[en]);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

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