oj.uz

Submission #212694

# Submission time Handle Problem Language Result Execution time Memory
212694 2020-03-24T06:32:15 Z SorahISA Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 684 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);
    
    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

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 71 ms 110968 KB Output is correct
2 Correct 71 ms 110968 KB Output is correct
3 Correct 72 ms 110968 KB Output is correct
4 Correct 76 ms 110968 KB Output is correct
5 Correct 74 ms 110968 KB Output is correct
6 Correct 72 ms 110968 KB Output is correct
7 Correct 73 ms 110968 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 110968 KB Output is correct
2 Correct 73 ms 110968 KB Output is correct
3 Correct 72 ms 110968 KB Output is correct
4 Correct 71 ms 110968 KB Output is correct
5 Correct 72 ms 110968 KB Output is correct
6 Correct 71 ms 110968 KB Output is correct
7 Correct 73 ms 110968 KB Output is correct
8 Correct 72 ms 110968 KB Output is correct
9 Correct 72 ms 110968 KB Output is correct
10 Correct 76 ms 111356 KB Output is correct
11 Correct 133 ms 114808 KB Output is correct
12 Correct 232 ms 171512 KB Output is correct
13 Correct 268 ms 176248 KB Output is correct
14 Correct 124 ms 113272 KB Output is correct
15 Correct 126 ms 113272 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 110968 KB Output is correct
2 Correct 72 ms 110984 KB Output is correct
3 Correct 73 ms 110968 KB Output is correct
4 Correct 71 ms 110968 KB Output is correct
5 Correct 73 ms 110968 KB Output is correct
6 Correct 71 ms 110968 KB Output is correct
7 Correct 73 ms 110968 KB Output is correct
8 Correct 72 ms 110968 KB Output is correct
9 Correct 71 ms 110968 KB Output is correct
10 Correct 74 ms 111352 KB Output is correct
11 Correct 133 ms 114808 KB Output is correct
12 Correct 236 ms 171512 KB Output is correct
13 Correct 271 ms 176248 KB Output is correct
14 Correct 126 ms 113272 KB Output is correct
15 Correct 128 ms 113272 KB Output is correct
16 Correct 83 ms 111480 KB Output is correct
17 Correct 127 ms 115064 KB Output is correct
18 Correct 89 ms 111480 KB Output is correct
19 Correct 79 ms 111096 KB Output is correct
20 Runtime error 684 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 72 ms 110968 KB Output is correct
2 Correct 73 ms 110968 KB Output is correct
3 Correct 73 ms 110968 KB Output is correct
4 Correct 74 ms 110968 KB Output is correct
5 Correct 72 ms 110968 KB Output is correct
6 Correct 80 ms 111020 KB Output is correct
7 Correct 72 ms 110968 KB Output is correct
8 Correct 72 ms 110968 KB Output is correct
9 Correct 72 ms 110980 KB Output is correct
10 Correct 76 ms 111352 KB Output is correct
11 Correct 140 ms 114808 KB Output is correct
12 Correct 234 ms 171516 KB Output is correct
13 Correct 271 ms 176248 KB Output is correct
14 Correct 131 ms 113272 KB Output is correct
15 Correct 124 ms 113272 KB Output is correct
16 Correct 84 ms 111480 KB Output is correct
17 Correct 126 ms 115064 KB Output is correct
18 Correct 84 ms 111352 KB Output is correct
19 Correct 77 ms 111096 KB Output is correct
20 Runtime error 682 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 72 ms 110968 KB Output is correct
2 Correct 74 ms 110968 KB Output is correct
3 Correct 72 ms 110968 KB Output is correct
4 Correct 79 ms 110968 KB Output is correct
5 Correct 73 ms 110968 KB Output is correct
6 Correct 73 ms 110968 KB Output is correct
7 Correct 76 ms 110968 KB Output is correct
8 Correct 76 ms 110968 KB Output is correct
9 Correct 72 ms 110968 KB Output is correct
10 Correct 77 ms 111352 KB Output is correct
11 Correct 133 ms 114808 KB Output is correct
12 Correct 239 ms 171512 KB Output is correct
13 Correct 279 ms 176328 KB Output is correct
14 Correct 124 ms 113248 KB Output is correct
15 Correct 125 ms 113272 KB Output is correct
16 Correct 82 ms 111476 KB Output is correct
17 Correct 125 ms 115064 KB Output is correct
18 Correct 91 ms 111608 KB Output is correct
19 Correct 77 ms 111224 KB Output is correct
20 Runtime error 680 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -