제출 #634739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634739		ljuba	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	762 ms	67320 KiB

skyscraper

#include <bits/stdc++.h>
#include <queue>
#include <ratio>
 
using namespace std;
 
using ll = long long;
 
const int INF = 1e9 + 12;
 
const int K = 174;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    //sqrt decomposition + dijkstra?
 
    vector<pair<int, int>> v(m);
 
    for(auto &z : v) {
        cin >> z.first >> z.second;
    }
 
    vector<pair<int, int>> which[K + 2][K + 2];
 
    for(auto &z : v) {
        for(int i = 1; i < K; ++i) {
            which[i][z.first % i].push_back(z);
        }
    }
 
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
 
    int ans = INF;
 
    pq.push({0, v[0]});
 
    set<pair<int, int>> visited;
    // visited.insert(v[0]);
 
    vector<pair<int, int>> where[n];
 
    for(auto z : v) {
        where[z.first].push_back(z);
    }
 
    while(!pq.empty()) {
        auto best = pq.top();
        auto current = best.second;
        pq.pop();
 
        if(visited.count(current)) continue;
        visited.insert(current);
 
        // cerr << best.first << " " << best.second.first << " " << best.second.second << endl;
 
        if(current == v[1]) {
            ans = min(ans, best.first);
            break;
        }

        if(current.second < K) {
            if(current.second == 0) {
                for(auto z : where[current.first]) {
                    if(!visited.count(z)) {
                        pq.push({best.first, z});
                    }
                }

                where[current.first].clear();
            } else {
                for(auto z : which[current.second][current.first % current.second]) {
                    int raz = abs(z.first - current.first);
                    if(current.second == 0 && raz != 0) continue;
                    raz /= current.second;
    
                    if(!visited.count(z)) {
                        pq.push({best.first + raz, z});
                        // visited.insert(z);
                    }
                }
    
                // which[current.second][current.first % current.second].clear();
            }
        } else {
            for(int i = current.first; i < n; i += current.second) {
                for(auto z : where[i]) {
                    int raz = abs(z.first - current.first);
                    if(current.second == 0 && raz != 0) continue;
                    raz /= current.second;
 
                    if(!visited.count(z)) {
                        pq.push({best.first + raz, z});
                        // visited.insert(z);
                    }
                }
 
                where[i].clear();
            }
 
            for(int i = current.first - current.second; i >= 0; i -= current.second) {
                for(auto z : where[i]) {
                    int raz = abs(z.first - current.first);
                    if(current.second == 0 && raz != 0) continue;
                    raz /= current.second;
 
                    if(!visited.count(z)) {
                        pq.push({best.first + raz, z});
                        // visited.insert(z);
                    }
                }
 
                where[i].clear();
            }
        }
    }
 
    cout << ((ans >= INF) ? -1 : ans) << '\n';
}
 
/*
3 4
2 1
0 1
0 2
2 2
*/

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