oj.uz

Submission #779979

# Submission time Handle Problem Language Result Execution time Memory
779979 2023-07-12T04:45:44 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 262 ms 262144 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];
vector<pair<int, int>> adj[5000005], doge;
int mp[2005][2005];

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[x1][p1] == -1) {
            mp[x1][p1] = idx++;
        }
        if (mp[x2][p2] == -1) {
            mp[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();
        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);

    fill(&mp[0][0], &mp[0][0] + sizeof(mp) / sizeof(mp[0][0]), -1);

    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);
        }
        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(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 63 ms 152952 KB Output is correct
2 Correct 63 ms 153020 KB Output is correct
3 Correct 69 ms 153008 KB Output is correct
4 Correct 62 ms 152976 KB Output is correct
5 Correct 63 ms 152908 KB Output is correct
6 Correct 63 ms 153004 KB Output is correct
7 Correct 65 ms 153004 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 152896 KB Output is correct
2 Correct 62 ms 152908 KB Output is correct
3 Correct 61 ms 152956 KB Output is correct
4 Correct 63 ms 152924 KB Output is correct
5 Correct 72 ms 152996 KB Output is correct
6 Correct 63 ms 152980 KB Output is correct
7 Correct 63 ms 152956 KB Output is correct
8 Correct 63 ms 152960 KB Output is correct
9 Correct 63 ms 152912 KB Output is correct
10 Correct 64 ms 153124 KB Output is correct
11 Correct 65 ms 153336 KB Output is correct
12 Correct 76 ms 159000 KB Output is correct
13 Correct 71 ms 159308 KB Output is correct
14 Correct 64 ms 153348 KB Output is correct
15 Correct 66 ms 153232 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 152912 KB Output is correct
2 Correct 64 ms 153020 KB Output is correct
3 Correct 63 ms 152968 KB Output is correct
4 Correct 75 ms 152920 KB Output is correct
5 Correct 65 ms 152976 KB Output is correct
6 Correct 64 ms 152912 KB Output is correct
7 Correct 65 ms 152960 KB Output is correct
8 Correct 64 ms 152908 KB Output is correct
9 Correct 65 ms 153032 KB Output is correct
10 Correct 71 ms 153016 KB Output is correct
11 Correct 66 ms 153420 KB Output is correct
12 Correct 72 ms 159048 KB Output is correct
13 Correct 70 ms 159296 KB Output is correct
14 Correct 64 ms 153340 KB Output is correct
15 Correct 65 ms 153356 KB Output is correct
16 Correct 64 ms 153276 KB Output is correct
17 Correct 68 ms 154020 KB Output is correct
18 Correct 65 ms 153340 KB Output is correct
19 Correct 64 ms 153244 KB Output is correct
20 Runtime error 262 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 152904 KB Output is correct
2 Correct 63 ms 152992 KB Output is correct
3 Correct 64 ms 152948 KB Output is correct
4 Correct 69 ms 152988 KB Output is correct
5 Correct 70 ms 153152 KB Output is correct
6 Correct 63 ms 152996 KB Output is correct
7 Correct 64 ms 152904 KB Output is correct
8 Correct 63 ms 153000 KB Output is correct
9 Correct 63 ms 152948 KB Output is correct
10 Correct 64 ms 153120 KB Output is correct
11 Correct 67 ms 153508 KB Output is correct
12 Correct 70 ms 159032 KB Output is correct
13 Correct 71 ms 159220 KB Output is correct
14 Correct 64 ms 153348 KB Output is correct
15 Correct 72 ms 153320 KB Output is correct
16 Correct 64 ms 153280 KB Output is correct
17 Correct 72 ms 154032 KB Output is correct
18 Correct 66 ms 153360 KB Output is correct
19 Correct 64 ms 153144 KB Output is correct
20 Runtime error 228 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 152932 KB Output is correct
2 Correct 65 ms 152912 KB Output is correct
3 Correct 63 ms 153008 KB Output is correct
4 Correct 65 ms 153016 KB Output is correct
5 Correct 63 ms 152968 KB Output is correct
6 Correct 65 ms 152932 KB Output is correct
7 Correct 73 ms 152992 KB Output is correct
8 Correct 64 ms 152968 KB Output is correct
9 Correct 63 ms 153036 KB Output is correct
10 Correct 64 ms 153108 KB Output is correct
11 Correct 65 ms 153368 KB Output is correct
12 Correct 84 ms 159068 KB Output is correct
13 Correct 70 ms 159232 KB Output is correct
14 Correct 68 ms 153340 KB Output is correct
15 Correct 66 ms 153292 KB Output is correct
16 Correct 63 ms 153156 KB Output is correct
17 Correct 67 ms 153976 KB Output is correct
18 Correct 64 ms 153328 KB Output is correct
19 Correct 67 ms 153292 KB Output is correct
20 Runtime error 245 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -