Submission #876861

#	Time	Username	Problem	Language	Result	Execution time	Memory
876861		Beerus13	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	106 ms	5456 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e4 + 5;
const int sqr = 105;

int n, m, s, t, dp[N];
bool vs[sqr][N];
vector<int> g[N];

struct node {
    int vt, step, cost;
    node(int vt, int step, int cost) : vt(vt), step(step), cost(cost) {}
};

void bfs(int u) {
    memset(dp, -1, sizeof(dp));
    queue<node> q; q.emplace(u, 0, 0);
    while(q.size()) {
        auto [vt, step, cost] = q.front(); q.pop();
        if(vt < 0 || vt >= n) continue;
        int p = abs(step);
        if(p < sqr && vs[p][vt]) continue;
        if(p < sqr) vs[p][vt] = 1;
        q.emplace(vt + step, step, cost + 1);
        if(dp[vt] == -1) {
            dp[vt] = cost;
            for(int power : g[vt]) {
                q.emplace(vt + power, power, cost + 1);
                q.emplace(vt - power, -power, cost + 1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; ++i) {
        int vt, step; cin >> vt >> step;
        g[vt].push_back(step);
        if(i == 0) s = vt;
        if(i == 1) t = vt;
    }
    bfs(s); 
    cout << dp[t] << '\n';
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void bfs(int)':
skyscraper.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |         auto [vt, step, cost] = q.front(); q.pop();
      |              ^

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