제출 #1031134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031134		_8_8_	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	616 ms	262392 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 20, MOD = (int)1e9+7;

int n,m,b[N],p[N],ft[N];
vector<pair<int,int>> x[N],g[N * 5];
void add(int v,int u) {
    g[v].push_back({u,1});
    g[u].push_back({v,1});
}
int d[N * 5];
void test() {
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        cin >> b[i] >> p[i];
        int d = b[i] % p[i];
        x[p[i]].emplace_back(d,i);
    }
    int it = n - 1;
    for(int i = 1;i < n;i++){
        sort(x[i].begin(),x[i].end());
        for(int j = 0;j < (int)x[i].size();j++){
            if(!j || x[i][j].first != x[i][j - 1].first){
                // cout << i << ' ';
                for(int k = x[i][j].first;k < n;k += i){
                    ft[k] = ++it;
                    if(k - i >= 0){
                        add(ft[k - i],ft[k]);
                    }
                    g[ft[k]].push_back({k,0});
                }
            }
            int v = b[x[i][j].second];
            g[v].push_back({ft[v],0});
        }
        // cout << '\n';
    }
    set<pair<int,int>> st;
    for(int i = 0;i <= it;i++){
        d[i] = 1e9;
    }
    st.insert({0,b[0]});
    d[b[0]] = 0;
    while(!st.empty()){
        auto [c,v] = (*st.begin());
        st.erase(st.begin());
        for(auto [to,w]:g[v]){
            if(d[to] > d[v] + w){
                st.erase({d[to],to});
                d[to] = d[v] + w;
                st.insert({d[to],to});
            }
        }
    }
    if(d[b[1]] == 1e9){
        d[b[1]] = -1;
    }
    cout << d[b[1]];
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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