Submission #380642

#	Time	Username	Problem	Language	Result	Execution time	Memory
380642		dannyboy20031204	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1096 ms	88684 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 200, inf = 1e9 + 7; //
#define node pair<pair<int, int>, int>
#define mode first.first
#define a first.second
#define b second
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int x[m], d[m];
    map<node, bool> vis;
    map<node, int> dis;
    vector<int> on[n];
    for (int i = 0; i < m; i++){
        cin >> x[i] >> d[i];
        on[x[i]].push_back(i);
    }
    deque<node> q;
    if (d[0] < N) q.push_back({{0, d[0]}, x[0]});
    else q.push_back({{1, 0}, x[0]});
    vis[q.front()] = true;
    while (!q.empty()){
        node u = q.front();
        q.pop_front();
        //cout << dis[u] << ' ' << u.a << ' ' << u.b << ' ' << '\n';
        if (u.mode == 0){
            if (u.b + u.a < n and !vis[{{0, u.a}, u.b + u.a}]){
                q.push_back({{0, u.a}, u.b + u.a});
                dis[{{0, u.a}, u.b + u.a}] = dis[u] + 1;
                vis[{{0, u.a}, u.b + u.a}] = true;
            }
            if (u.b - u.a >= 0 and !vis[{{0, u.a}, u.b - u.a}]){
                q.push_back({{0, u.a}, u.b - u.a});
                dis[{{0, u.a}, u.b - u.a}] = dis[u] + 1;
                vis[{{0, u.a}, u.b - u.a}] = true;
            }
        }
        else {
            if (u.b + d[u.a] < n and !vis[{{1, u.a}, u.b + d[u.a]}]){
                q.push_back({{1, u.a}, u.b + d[u.a]});
                dis[{{1, u.a}, u.b + d[u.a]}] = dis[u] + 1;
                vis[{{1, u.a}, u.b + d[u.a]}] = true;
            }
            if (u.b - d[u.a] >= 0 and !vis[{{1, u.a}, u.b - d[u.a]}]){
                q.push_back({{1, u.a}, u.b - d[u.a]});
                dis[{{1, u.a}, u.b - d[u.a]}] = dis[u] + 1;
                vis[{{1, u.a}, u.b - d[u.a]}] = true;
            }
        }
        while (!on[u.b].empty()){
            int v = on[u.b].back();
            on[u.b].pop_back();
            if (d[v] < N and !vis[{{0, d[v]}, u.b}]){
                dis[{{0, d[v]}, u.b}] = dis[u];
                vis[{{0, d[v]}, u.b}] = true;
                q.push_front({{0, d[v]}, u.b});
            }
            else if (d[v] >= N and !vis[{{1, v}, u.b}]){
                dis[{{1, v}, u.b}] = dis[u];
                vis[{{1, v}, u.b}] = true;
                q.push_front({{1, v}, u.b});
            }
        }
        if (u.b == x[1]){
            cout << dis[u];
            return 0;
        }
    }
    cout << -1;
}

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