oj.uz

Submission #778953

# Submission time Handle Problem Language Result Execution time Memory
778953 2023-07-11T05:11:08 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 179668 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <bitset>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
    #define D(...)
#endif

int n, m, idx, dist[5000005];
bool seen[5000005];
vector<pair<int, int>> adj[5000005], doge;
map<pair<int, int>, int> mp;

void connect(int x1, int p1, int x2, int p2, int d) {
    if (x2 >= 0 && x2 <= n - 1 && x1 >= 0 && x1 <= n - 1) {
        if (!mp.count({x1, p1})) {
            mp.insert({{x1, p1}, idx++}); 
        }
        if (!mp.count({x2, p2})) {
            mp.insert({{x2, p2}, idx++});
        }
        adj[mp[{x1, p1}]].push_back({mp[{x2, p2}], d});
    }
}
 
void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fill(dist, dist + 5000005, 2e9);
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int curr = pq.top().s;
        pq.pop();
        if (seen[curr]) continue;
        seen[curr] = true;
        for (auto [i, d] : adj[curr]) {
            if (dist[curr] + d < dist[i]) {
                dist[i] = dist[curr] + d;
                pq.push({dist[i], i});
            }
        }
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0, b, p; i < m; i++) {
        cin >> b >> p;
        for (int j = b; j >= 0; j -= p) {
            connect(j, p, j - p, 0, 1);
            connect(j, p, j + p, 0, 1);
            connect(j, p, j - p, p, 1);
            connect(j - p, p, j, p, 1);
        }
        for (int j = b; j <= n - 1; j += p) {
            if (j > b) {
                connect(j, p, j - p, 0, 1);
                connect(j, p, j + p, 0, 1);
            }
            connect(j, p, j + p, p, 1);
            connect(j + p, p, j, p, 1);
        }
        connect(b, 0, b, p, 0);
        connect(b, p, b, 0, 0);
        doge.push_back({b, p});
    }

    dijkstra(mp[{doge[0].f, 0}]);

    cout << (dist[mp[{doge[1].f, doge[1].s}]] == 2e9 ? -1 : dist[mp[{doge[1].f, doge[1].s}]]) << "\n";


}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 137220 KB Output is correct
2 Correct 56 ms 137280 KB Output is correct
3 Correct 56 ms 137292 KB Output is correct
4 Correct 59 ms 137300 KB Output is correct
5 Correct 61 ms 137228 KB Output is correct
6 Correct 64 ms 137208 KB Output is correct
7 Correct 58 ms 137304 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 137192 KB Output is correct
2 Correct 58 ms 137292 KB Output is correct
3 Correct 58 ms 137252 KB Output is correct
4 Correct 59 ms 137288 KB Output is correct
5 Correct 60 ms 137316 KB Output is correct
6 Correct 64 ms 137304 KB Output is correct
7 Correct 60 ms 137196 KB Output is correct
8 Correct 58 ms 137292 KB Output is correct
9 Correct 60 ms 137292 KB Output is correct
10 Correct 66 ms 137572 KB Output is correct
11 Correct 71 ms 138260 KB Output is correct
12 Correct 166 ms 144032 KB Output is correct
13 Correct 146 ms 144224 KB Output is correct
14 Correct 66 ms 137932 KB Output is correct
15 Correct 66 ms 137964 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 137248 KB Output is correct
2 Correct 58 ms 137244 KB Output is correct
3 Correct 57 ms 137232 KB Output is correct
4 Correct 58 ms 137212 KB Output is correct
5 Correct 60 ms 137304 KB Output is correct
6 Correct 69 ms 137292 KB Output is correct
7 Correct 67 ms 137368 KB Output is correct
8 Correct 60 ms 137312 KB Output is correct
9 Correct 59 ms 137220 KB Output is correct
10 Correct 61 ms 137504 KB Output is correct
11 Correct 73 ms 138060 KB Output is correct
12 Correct 152 ms 144016 KB Output is correct
13 Correct 139 ms 144240 KB Output is correct
14 Correct 73 ms 137960 KB Output is correct
15 Correct 68 ms 138020 KB Output is correct
16 Correct 68 ms 137808 KB Output is correct
17 Correct 91 ms 139260 KB Output is correct
18 Correct 71 ms 138172 KB Output is correct
19 Correct 67 ms 137932 KB Output is correct
20 Execution timed out 1076 ms 177992 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 137260 KB Output is correct
2 Correct 61 ms 137260 KB Output is correct
3 Correct 62 ms 137236 KB Output is correct
4 Correct 62 ms 137300 KB Output is correct
5 Correct 65 ms 137200 KB Output is correct
6 Correct 63 ms 137284 KB Output is correct
7 Correct 72 ms 137240 KB Output is correct
8 Correct 64 ms 137316 KB Output is correct
9 Correct 62 ms 137280 KB Output is correct
10 Correct 65 ms 137420 KB Output is correct
11 Correct 79 ms 138032 KB Output is correct
12 Correct 153 ms 143944 KB Output is correct
13 Correct 142 ms 144228 KB Output is correct
14 Correct 71 ms 138032 KB Output is correct
15 Correct 70 ms 138084 KB Output is correct
16 Correct 70 ms 137740 KB Output is correct
17 Correct 92 ms 139348 KB Output is correct
18 Correct 78 ms 138172 KB Output is correct
19 Correct 80 ms 137908 KB Output is correct
20 Execution timed out 1086 ms 179668 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 137300 KB Output is correct
2 Correct 65 ms 137300 KB Output is correct
3 Correct 65 ms 137304 KB Output is correct
4 Correct 62 ms 137296 KB Output is correct
5 Correct 62 ms 137292 KB Output is correct
6 Correct 73 ms 137304 KB Output is correct
7 Correct 63 ms 137276 KB Output is correct
8 Correct 63 ms 137284 KB Output is correct
9 Correct 63 ms 137288 KB Output is correct
10 Correct 65 ms 137444 KB Output is correct
11 Correct 85 ms 138100 KB Output is correct
12 Correct 157 ms 143948 KB Output is correct
13 Correct 141 ms 144244 KB Output is correct
14 Correct 69 ms 137932 KB Output is correct
15 Correct 72 ms 138012 KB Output is correct
16 Correct 70 ms 137836 KB Output is correct
17 Correct 94 ms 139316 KB Output is correct
18 Correct 85 ms 138112 KB Output is correct
19 Correct 68 ms 137964 KB Output is correct
20 Execution timed out 1069 ms 178944 KB Time limit exceeded
21 Halted 0 ms 0 KB -