Submission #380644

#	Time	Username	Problem	Language	Result	Execution time	Memory
380644		dannyboy20031204	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	40 ms	21740 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 150, inf = 1e9 + 7; //
#define node pair<pair<int, int>, int>
#define mode first.first
#define a first.second
#define b second
int n, m;
int f(node i){
    if (i.mode == 0) return n * i.a + i.b;
    else return N * i.a + i.b / N;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    int x[m], d[m];
    bitset<200 * 30000> vis[2]{};
    int dis[2][200 * 30000];
    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[d[0] < N ? 0 : 1][f(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][f({{0, u.a}, u.b + u.a})]){
                q.push_back({{0, u.a}, u.b + u.a});
                dis[0][f({{0, u.a}, u.b + u.a})] = dis[0][f(u)] + 1;
                vis[0][f({{0, u.a}, u.b + u.a})] = true;
            }
            if (u.b - u.a >= 0 and !vis[0][f({{0, u.a}, u.b - u.a})]){
                q.push_back({{0, u.a}, u.b - u.a});
                dis[0][f({{0, u.a}, u.b - u.a})] = dis[0][f(u)] + 1;
                vis[0][f({{0, u.a}, u.b - u.a})] = true;
            }
        }
        else {
            if (u.b + d[u.a] < n and !vis[1][f({{1, u.a}, u.b + d[u.a]})]){
                q.push_back({{1, u.a}, u.b + d[u.a]});
                dis[1][f({{1, u.a}, u.b + d[u.a]})] = dis[1][f(u)] + 1;
                vis[1][f({{1, u.a}, u.b + d[u.a]})] = true;
            }
            if (u.b - d[u.a] >= 0 and !vis[1][f({{1, u.a}, u.b - d[u.a]})]){
                q.push_back({{1, u.a}, u.b - d[u.a]});
                dis[1][f({{1, u.a}, u.b - d[u.a]})] = dis[1][f(u)] + 1;
                vis[1][f({{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][f({{0, d[v]}, u.b})]){
                dis[0][f({{0, d[v]}, u.b})] = dis[u.mode][f(u)];
                vis[0][f({{0, d[v]}, u.b})] = true;
                q.push_front({{0, d[v]}, u.b});
            }
            else if (d[v] >= N and !vis[1][f({{1, v}, u.b})]){
                dis[1][f({{1, v}, u.b})] = dis[u.mode][f(u)];
                vis[1][f({{1, v}, u.b})] = true;
                q.push_front({{1, v}, u.b});
            }
        }
        if (u.b == x[1]){
            cout << dis[u.mode][f(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