oj.uz

답안 #212703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212703 2020-03-24T07:00:57 Z SorahISA Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 1000 ms 54848 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;

map<int, vector<pii>> adj;
map<int, int> dis;
map<int, bool> vis;
prior<pii> pq;

void dijkstra(int now) {
    for (auto [id, cost] : adj[now]) {
        if (vis[id]) continue;
        if (dis[id] == 0 or 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)] = 1, 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)] == 0 ? INF : dis[tr(1, i)]-1);
    }
    
    cout << (minAns == INF ? -1 : minAns) << "\n";
    
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 11 ms 1024 KB Output is correct
11 Correct 128 ms 5880 KB Output is correct
12 Execution timed out 1095 ms 54848 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 11 ms 1024 KB Output is correct
11 Correct 129 ms 5884 KB Output is correct
12 Execution timed out 1100 ms 54776 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 11 ms 1024 KB Output is correct
11 Correct 137 ms 5884 KB Output is correct
12 Execution timed out 1092 ms 54692 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 11 ms 1024 KB Output is correct
11 Correct 134 ms 5864 KB Output is correct
12 Execution timed out 1095 ms 54796 KB Time limit exceeded
13 Halted 0 ms 0 KB -