Submission #52731

#	Time	Username	Problem	Language	Result	Execution time	Memory
52731		chpipis	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	137 ms	17628 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int SIZE = 175;
const int MAXN = 3e4 + 5;
const int INF = 1e9;

bool dist[MAXN][SIZE];
deque<pair<int, ii> > deq;
bool visit[MAXN];
vi vec[MAXN];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n, m, st = -1, en = -1;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int b, p;
        scanf("%d %d", &b, &p);
        vec[b].pb(p);
        if (i == 0) {
            st = b;
            if (p < SIZE) {
                dist[st][p] = true;
            } else {
                deq.pb(mp(0, mp(st, -p)));
            }
            deq.pb(mp(0, mp(st, p)));
        }
        if (i == 1) en = b;
    }
    //memset(dist, false, sizeof dist);
    /*
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < SIZE; j++)
            dist[i][j] = INF;
    */
    int ans = -1;
    while (!deq.empty()) {
        int w = deq.front().fi;
        int u = deq.front().se.fi;
        int x = deq.front().se.se;
        deq.pop_front();

        if (u == en) {
            ans = w;
            break;
        }

        if (x < 0 || x >= SIZE) {
            if (0 <= u + x && u + x < n) {
                deq.pb(mp(w + 1, mp(u + x, x)));
            }
        } else {
            if (u - x >= 0 && !dist[u - x][x]) {
                dist[u - x][x] = true;
                deq.pb(mp(w + 1, mp(u - x, x)));
            }
            if (u + x < n && !dist[u + x][x]) {
                dist[u + x][x] = true;
                deq.pb(mp(w + 1, mp(u + x, x)));
            }
        }

        if (visit[u]) continue;
        visit[u] = true;

        for (auto it : vec[u]) {
            if (it < SIZE) {
                if (!dist[u][it]) {
                    dist[u][it] = true;
                    deq.pf(mp(w, mp(u, it)));
                }
            } else {
                deq.pf(mp(w, mp(u, it)));
                deq.pf(mp(w, mp(u, -it)));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:70: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:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &b, &p);
         ~~~~~^~~~~~~~~~~~~~~~~

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