Submission #1186687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186687		icebear	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	20 ms	5324 KiB

skyscraper

// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"
#define index loveat

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 30000 + 5;
int n, m;
vector<int> G[N];
int dist[N], index[N], far[N];
map<int, bool> have[N];

void init(void) {
    cin >> n >> m;
    REP(i, m) {
        cin >> index[i] >> far[i];
        G[index[i]].pb(far[i]);
        have[index[i]][far[i]] = true;
    }
    REP(i, n) {
        sort(all(G[i]));
        G[i].resize(unique(all(G[i])) - G[i].begin());
    }
}

void process(void) {
    priority_queue<ii, vector<ii>, greater<ii>> Q;
    memset(dist, 0x3f, sizeof dist);
    dist[index[0]] = 0;
    Q.push(mp(0, index[0]));
    while(!Q.empty()) {
        int du, u; tie(du, u) = Q.top();
        Q.pop();
        if (du != dist[u]) continue;
        if (u == index[1]) {
            cout << du;
            return;
        }
        for(int jump : G[u]) {
            for(int w = 1; u + w * jump < n; w++) {
                int v = u + w * jump;
                if (!have[v].empty() && minimize(dist[v], du + w))
                    Q.push(mp(du + w, v));
                if (have[v].find(jump) != have[v].end()) break;
            }

            for(int w = 1; u - w * jump >= 0; w++) {
                int v = u - w * jump;
                if (!have[v].empty() && minimize(dist[v], du + w))
                    Q.push(mp(du + w, v));
                if (have[v].find(jump) != have[v].end()) break;
            }
        }
    }

    cout << -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         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