oj.uz

Submission #212704

# Submission time Handle Problem Language Result Execution time Memory
212704 2020-03-24T07:02:43 Z SorahISA Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 697 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 = 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);
    
    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 69 ms 110968 KB Output is correct
2 Correct 68 ms 110968 KB Output is correct
3 Correct 74 ms 110968 KB Output is correct
4 Correct 72 ms 110968 KB Output is correct
5 Correct 69 ms 110968 KB Output is correct
6 Correct 68 ms 110968 KB Output is correct
7 Correct 69 ms 110968 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 110968 KB Output is correct
2 Correct 71 ms 111224 KB Output is correct
3 Correct 69 ms 110968 KB Output is correct
4 Correct 67 ms 110968 KB Output is correct
5 Correct 69 ms 110968 KB Output is correct
6 Correct 69 ms 110968 KB Output is correct
7 Correct 69 ms 110968 KB Output is correct
8 Correct 71 ms 111096 KB Output is correct
9 Correct 69 ms 111096 KB Output is correct
10 Correct 72 ms 111352 KB Output is correct
11 Correct 132 ms 114808 KB Output is correct
12 Correct 231 ms 171512 KB Output is correct
13 Correct 267 ms 176376 KB Output is correct
14 Correct 120 ms 113272 KB Output is correct
15 Correct 119 ms 113272 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 110968 KB Output is correct
2 Correct 67 ms 110968 KB Output is correct
3 Correct 68 ms 110968 KB Output is correct
4 Correct 76 ms 110968 KB Output is correct
5 Correct 69 ms 110968 KB Output is correct
6 Correct 70 ms 110896 KB Output is correct
7 Correct 68 ms 110968 KB Output is correct
8 Correct 69 ms 110968 KB Output is correct
9 Correct 69 ms 110968 KB Output is correct
10 Correct 71 ms 111352 KB Output is correct
11 Correct 127 ms 114808 KB Output is correct
12 Correct 238 ms 171756 KB Output is correct
13 Correct 260 ms 176248 KB Output is correct
14 Correct 121 ms 113276 KB Output is correct
15 Correct 120 ms 113284 KB Output is correct
16 Correct 80 ms 111480 KB Output is correct
17 Correct 120 ms 115100 KB Output is correct
18 Correct 80 ms 111228 KB Output is correct
19 Correct 74 ms 111220 KB Output is correct
20 Runtime error 697 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 110968 KB Output is correct
2 Correct 68 ms 110968 KB Output is correct
3 Correct 69 ms 110968 KB Output is correct
4 Correct 67 ms 110968 KB Output is correct
5 Correct 67 ms 110968 KB Output is correct
6 Correct 69 ms 110968 KB Output is correct
7 Correct 67 ms 110968 KB Output is correct
8 Correct 68 ms 110968 KB Output is correct
9 Correct 67 ms 110968 KB Output is correct
10 Correct 71 ms 111352 KB Output is correct
11 Correct 128 ms 114808 KB Output is correct
12 Correct 229 ms 171512 KB Output is correct
13 Correct 265 ms 176248 KB Output is correct
14 Correct 122 ms 113272 KB Output is correct
15 Correct 122 ms 113272 KB Output is correct
16 Correct 84 ms 111480 KB Output is correct
17 Correct 120 ms 115000 KB Output is correct
18 Correct 80 ms 111224 KB Output is correct
19 Correct 82 ms 111224 KB Output is correct
20 Runtime error 690 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 110968 KB Output is correct
2 Correct 68 ms 110972 KB Output is correct
3 Correct 73 ms 111224 KB Output is correct
4 Correct 67 ms 110968 KB Output is correct
5 Correct 68 ms 110968 KB Output is correct
6 Correct 67 ms 110968 KB Output is correct
7 Correct 68 ms 110972 KB Output is correct
8 Correct 68 ms 110968 KB Output is correct
9 Correct 75 ms 110968 KB Output is correct
10 Correct 72 ms 111352 KB Output is correct
11 Correct 130 ms 114808 KB Output is correct
12 Correct 229 ms 171512 KB Output is correct
13 Correct 273 ms 176248 KB Output is correct
14 Correct 122 ms 113264 KB Output is correct
15 Correct 120 ms 113236 KB Output is correct
16 Correct 78 ms 111480 KB Output is correct
17 Correct 120 ms 115064 KB Output is correct
18 Correct 81 ms 111352 KB Output is correct
19 Correct 73 ms 111224 KB Output is correct
20 Runtime error 693 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -