Submission #700886

#	Time	Username	Problem	Language	Result	Execution time	Memory
700886		nguyentunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	336 ms	225980 KiB

skyscraper

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 3e4 + 10, M = 1e9;
bool dd[M];
vector<int> lst[N];
int cnt;
bool mark[N];
bool id(int x, int y) {
    int code = x * (3e4 + 1) + y;
    if (dd[code]) return 1;
    dd[code] = 1;
    return 0;
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n, m; cin >> n >> m;
    pair<int, int> st, ed;
    for(int i = 0; i < m; i++) {
        int b, p; cin >> b >> p;
        lst[b].push_back(p);
        if (i == 0) st = make_pair(b, p);
        if (i == 1) ed = make_pair(b, p);
    }
    deque<tuple<int, int, int> > dq;
    id(st.fi, st.se);
    dq.push_back({0, st.fi, st.se});

    while (!dq.empty()) {
        auto [cost, pos, jump] = dq.front(); dq.pop_front();
        if (pos == ed.fi) return cout << cost, 0;
        if (!mark[pos]) {
            for(auto &j : lst[pos]) {
                if (!id(pos, j)) dq.push_front({cost, pos, j});
            }
            mark[pos] = 1;
        }
        if (pos + jump < n) {
            if (!id(pos + jump, jump)) dq.push_back({cost + 1, pos + jump, jump});
        }
        if (pos - jump >= 0) {
            if (!id(pos - jump, jump)) dq.push_back({cost + 1, pos - jump, jump});
        }
    }
    cout << -1;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:23:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:26:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:27:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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