oj.uz

Submission #212702

# Submission time Handle Problem Language Result Execution time Memory
212702 2020-03-24T06:57:36 Z SorahISA Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 218 ms 262148 KB 
// #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 = 3000 + 5;
const int maxm = 3000 + 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);
    
    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);
            }
        }
    }
    
    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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 248824 KB Output is correct
2 Correct 146 ms 248824 KB Output is correct
3 Correct 149 ms 248824 KB Output is correct
4 Correct 145 ms 248824 KB Output is correct
5 Correct 146 ms 248824 KB Output is correct
6 Correct 146 ms 248824 KB Output is correct
7 Correct 145 ms 248884 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 248872 KB Output is correct
2 Correct 159 ms 248952 KB Output is correct
3 Correct 147 ms 248824 KB Output is correct
4 Correct 146 ms 248824 KB Output is correct
5 Correct 147 ms 248824 KB Output is correct
6 Correct 148 ms 248840 KB Output is correct
7 Correct 145 ms 248824 KB Output is correct
8 Correct 145 ms 248824 KB Output is correct
9 Correct 151 ms 248824 KB Output is correct
10 Correct 154 ms 249464 KB Output is correct
11 Correct 208 ms 252664 KB Output is correct
12 Runtime error 163 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 248824 KB Output is correct
2 Correct 147 ms 248824 KB Output is correct
3 Correct 148 ms 248824 KB Output is correct
4 Correct 148 ms 248824 KB Output is correct
5 Correct 152 ms 249080 KB Output is correct
6 Correct 145 ms 248824 KB Output is correct
7 Correct 147 ms 248824 KB Output is correct
8 Correct 146 ms 248824 KB Output is correct
9 Correct 160 ms 248952 KB Output is correct
10 Correct 150 ms 249288 KB Output is correct
11 Correct 214 ms 252664 KB Output is correct
12 Runtime error 158 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 248904 KB Output is correct
2 Correct 151 ms 248824 KB Output is correct
3 Correct 147 ms 248824 KB Output is correct
4 Correct 149 ms 248824 KB Output is correct
5 Correct 151 ms 248824 KB Output is correct
6 Correct 147 ms 248824 KB Output is correct
7 Correct 148 ms 248824 KB Output is correct
8 Correct 151 ms 248824 KB Output is correct
9 Correct 148 ms 248952 KB Output is correct
10 Correct 150 ms 249336 KB Output is correct
11 Correct 208 ms 252724 KB Output is correct
12 Runtime error 162 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 248828 KB Output is correct
2 Correct 170 ms 248828 KB Output is correct
3 Correct 146 ms 248824 KB Output is correct
4 Correct 149 ms 248824 KB Output is correct
5 Correct 148 ms 248824 KB Output is correct
6 Correct 147 ms 248828 KB Output is correct
7 Correct 145 ms 248828 KB Output is correct
8 Correct 146 ms 248844 KB Output is correct
9 Correct 146 ms 248824 KB Output is correct
10 Correct 151 ms 249208 KB Output is correct
11 Correct 218 ms 252752 KB Output is correct
12 Runtime error 165 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -