제출 #239148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239148		aggu_01000101	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1095 ms	74084 KiB

skyscraper

    #include <bits/stdc++.h>
    #define int long long
    #define INF 1000000000000
    #define lchild(i) (i*2 + 1)
    #define rchild(i) (i*2 + 2)
    #define mid(l, u) ((l+u)/2)
    #define x(p) p.first
    #define y(p) p.second
    #define MOD 998244353
    int n, m;
    using namespace std;

    signed main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        cin>>n>>m;
        int s = 0, t= 0;
        vector<int> adj[n];
        unordered_map<int, bool> ez[n];
        for(int i = 0;i<m;i++){
            int b, p;
            cin>>b>>p;
            if(!ez[b][p]) adj[b].push_back(p);
            ez[b][p] = true;
            if(i==0) s = b;
            if(i==1) t = b;
        }
        int dist[n];
        for(int i = 0;i<n;i++) dist[i] = INF;
        dist[s] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, s});
        while(!pq.empty()){
            pair<int, int> curr = pq.top();
            pq.pop();
            if(curr.first != dist[curr.second]) continue;
            for(int j: adj[curr.second]){
                int len = 0;
                for(int i = curr.second + j;i<n;i+=j){
                    len++;
                    if(curr.first + len < dist[i]){
                        dist[i] = curr.first + len;
                        pq.push({dist[i], i});
                    }
                    if(ez[i][j]) break;
                }
                len = 0;
                for(int i = curr.second - j;i>=0;i-=j){
                    len++;
                    if(curr.first + len < dist[i]){
                        dist[i] = curr.first + len;
                        pq.push({dist[i], i});
                    }
                    if(ez[i][j]) break;
                }
            }
        }
        if(dist[t]==INF) dist[t] = -1;
        cout<<dist[t]<<"\n";
    }

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