Submission #212694

#	Time	Username	Problem	Language	Result	Execution time	Memory
212694		SorahISA	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	684 ms	262148 KiB

skyscraper

// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")
 
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
 
#include <bits/stdc++.h>
using namespace std;
 
// #define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;
 
#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
 
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(0, 1); \
                 auto rnd = bind(__dis, __gen);
 
const int INF = 1E9;
const int mod = 1E9 + 7;
const int maxn = 2000 + 5;
const int maxm = 2000 + 5;

vector<pii> adj[maxn * maxm];
vector<int> dis(maxn * maxm, INF);
vector<bool> vis(maxn * maxm, 0);
prior<pii> pq;

void dijkstra(int now) {
    for (auto [id, cost] : adj[now]) {
        if (vis[id]) continue;
        if (dis[now] + cost < dis[id]) {
            dis[id] = dis[now] + cost;
            pq.push({dis[id], id});
        }
    }
    
    while (!pq.empty()) {
        auto [cost, id] = pq.top(); pq.pop();
        if (!vis[id]) vis[id] = 1, dijkstra(id);
    }
}

int32_t main() {
    fastIO();
    
    int n, m, b, p;
    cin >> n >> m;
    
    vector<pii> v;
    for (int i = 0; i < m; ++i) cin >> b >> p, v.eb(b, p);
    
    if (v[0].X == v[1].X) {
        cout << 0 << "\n";
        return 0;
    }
    
    auto tr = [&](int x, int y) {
        return x*n + y;
    };
    
    for (int i = 0; i < m; ++i) {
        for (int j = v[i].X%v[i].Y; j+v[i].Y < n; j += v[i].Y) {
            adj[tr(i, j)].eb(tr(i, j+v[i].Y), 1);
            adj[tr(i, j+v[i].Y)].eb(tr(i, j), 1);
        }
    }
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == j) continue;
            if ((v[i].X - v[j].X%v[j].Y) % v[j].Y == 0) {
                adj[tr(j, v[i].X)].eb(tr(i, v[i].X), 0);
            }
        }
    }
    
    /*
    for (int pl = 0; pl < n; ++pl) {
        for (int i = 0; i < m; ++i) {
            for (int j = i+1; j < m; ++j) {
                if ((pl - v[i].X%v[i].Y) % v[i].Y == 0 and
                    (pl - v[j].X%v[j].Y) % v[j].Y == 0) {
                    adj[tr(i, pl)].eb(tr(j, pl), abs(v[j].X-pl) / v[j].Y);
                    adj[tr(j, pl)].eb(tr(i, pl), abs(v[i].X-pl) / v[i].Y);
                }
            }
        }
    }
    */
    
    dis[tr(0, v[0].X)] = 0, vis[tr(0, v[0].X)] = 1, dijkstra(tr(0, v[0].X));
    
    int minAns = INF;
    for (int i = 0; i < n; ++i) {
        minAns = min(minAns, dis[tr(1, i)]);
    }
    
    cout << (minAns == INF ? -1 : minAns) << "\n";
    
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra(int)':
skyscraper.cpp:52:23: warning: unused variable 'cost' [-Wunused-variable]
         auto [cost, id] = pq.top(); pq.pop();
                       ^

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