Submission #1235911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235911		kss418	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1100 ms	105828 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/rope>
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define all(x) (x).begin(), (x).end()
#define x first 
#define y second
using namespace std; using ll = long long;
using ld = long double; using pld = pair<ld, ld>;
using i128 = __int128_t; using f128 = __float128; 
using pll = pair<ll, ll>; using tll = tuple<ll, ll, ll>;
ll n, m, k, t = 1; string s;

constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ll MINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll MAX = 30101; // SET MAX SIZE
constexpr ll MOD = 998244353;
pll a[MAX];
set <pll> num;

class _dij {
public:
    class node{
    public:
        ll d;
        node() : node(0){}
        node(ll d) : d(d){}
        ll num() const{ return d; }
        bool operator<(const node& ot) const{ return num() < ot.num(); }
        bool operator>(const node& ot) const{ return num() > ot.num(); }
        bool operator==(const node& ot) const{ return num() == ot.num(); }
        bool operator<=(const node& ot) const{ return num() <= ot.num(); }
        node operator+(const node& ot) const{
            return {d + ot.d};
        }
        operator ll(){ return d; }
    };
    node mx(){ return {INF}; }
    node mn(){ return {0}; }

    using ptl = pair <node, ll>;
    ll n; vector <node> d;
    vector <ll> pre;
    vector <vector<ptl>> adj;
    priority_queue <ptl, vector<ptl>, greater<ptl>> pq;

    _dij(){}
    _dij(ll n) { this->n = n; adj.resize(n + 1); }

    void add(ll st, ll en, node c) { // 양방향
        adj[st].push_back({ c,en });
        adj[en].push_back({ c,st });
    }
    void addsol(ll st, ll en, node c) { // 단방향
        adj[st].push_back({ c,en });
    }

    void init(ll st) {
        d.clear(); pre.clear();
        d.resize(n + 1, mx()); pre.resize(n + 1, -1); 
        pq.push({ mn(), st });
        d[st] = mn();

        while (!pq.empty()) {
            auto [cn, cur] = pq.top(); pq.pop();
            if(cn > d[cur]) continue;
            
            for (auto& i : adj[cur]) {
                auto [nn, nxt] = i;
                node pl = nn + cn;
        
                if (d[nxt] <= pl) continue;
                d[nxt] = pl; pre[nxt] = cur; 
                pq.push({ pl, nxt });
            }
        }
    }

    node ret(ll n) { return d[n]; }
};

unordered_map <ll, ll> mp[MAX];
deque <pll> q;
vector <ll> arr[MAX];

void run(){
    cin >> n >> m; _dij dij(n);
    for(int i = 1;i <= m;i++){
        cin >> a[i].x >> a[i].y;
        if(i != 1) arr[a[i].x].push_back(a[i].y);
    }

    q.push_back({a[1].x, a[1].y});
    mp[a[1].x][a[1].y] = 0;

    while(!q.empty()){
        auto[cur, cd] = q.front(); q.pop_front();
        if(cur - cd >= 0){
            if(!mp[cur - cd].count(cd)){
                q.push_back({cur - cd, cd});
                mp[cur - cd][cd] = mp[cur][cd] + 1;
            }
        }

        if(cur + cd < n){
            if(!mp[cur + cd].count(cd)){
                q.push_back({cur + cd, cd});
                mp[cur + cd][cd] = mp[cur][cd] + 1;
            }
        }

        for(auto& i : arr[cur]){
            if(mp[cur].count(i)) continue;
            q.push_front({cur, i});
            mp[cur][i] = mp[cur][cd];
        }
        arr[cur].clear();
    }
    
    ll result = INF;
    for(auto [idx, v] : mp[a[2].x]){
        result = min(result, v);
    }

    cout << (result == INF ? -1 : result);
}

int main() {
    fastio; // cin >> t;
    while(t--) run(); 

    return 0;
}

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