제출 #1031230

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

skyscraper

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

const int M = 3e4 + 21;
short n,m,b[M];
int ft[M];
vector<int> g[N];
vector<pair<short,short>> x[M];
void add(int v,int u) {
    g[v].push_back(u);
    g[u].push_back(v);
}
bool sgn(int x) {
    return (x < n);
}
int d[N];
void test() {
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        int p;
        cin >> b[i] >> p;
        int d = b[i] % p;
        x[p].emplace_back(d,i);
    }
    int it = n - 1;
    for(int i = 1;i < n;i++){
        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);
                }
            }
            int v = b[x[i][j].second];
            g[v].push_back(ft[v]);
        }
    }
    deque<int> q;
    for(int i = 0;i <= it;i++){
        d[i] = 1e9;
    }
    d[b[0]] = 0;
    q.push_front(b[0]);
    while(!q.empty()){
        int v = q[0];
        q.pop_front();
        for(int to:g[v]){
            int w = (sgn(v) == sgn(to));
            if(d[to] > d[v] + w){
                d[to] = d[v] + w;
                if(w == 0){
                    q.push_front(to);
                }else{
                    q.push_back(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