oj.uz

Submission #779974

# Submission time Handle Problem Language Result Execution time Memory
779974 2023-07-12T04:42:52 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 185 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[7000005];
bool seen[7000005];
vector<pair<int, int>> adj[7000005], 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 + 7000005, 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);

    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);
            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 83 ms 207828 KB Output is correct
2 Correct 96 ms 207780 KB Output is correct
3 Correct 98 ms 207820 KB Output is correct
4 Correct 85 ms 207704 KB Output is correct
5 Correct 86 ms 207820 KB Output is correct
6 Correct 97 ms 207824 KB Output is correct
7 Correct 85 ms 207776 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 207828 KB Output is correct
2 Correct 85 ms 207824 KB Output is correct
3 Correct 99 ms 207820 KB Output is correct
4 Correct 84 ms 207824 KB Output is correct
5 Correct 98 ms 207768 KB Output is correct
6 Correct 87 ms 207736 KB Output is correct
7 Correct 86 ms 207784 KB Output is correct
8 Correct 85 ms 207780 KB Output is correct
9 Correct 86 ms 207820 KB Output is correct
10 Correct 86 ms 207936 KB Output is correct
11 Correct 94 ms 208376 KB Output is correct
12 Correct 95 ms 214524 KB Output is correct
13 Correct 105 ms 214732 KB Output is correct
14 Correct 88 ms 208084 KB Output is correct
15 Correct 88 ms 208176 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 207844 KB Output is correct
2 Correct 86 ms 207752 KB Output is correct
3 Correct 93 ms 207720 KB Output is correct
4 Correct 95 ms 207720 KB Output is correct
5 Correct 85 ms 207732 KB Output is correct
6 Correct 86 ms 207820 KB Output is correct
7 Correct 90 ms 207712 KB Output is correct
8 Correct 89 ms 207800 KB Output is correct
9 Correct 86 ms 207836 KB Output is correct
10 Correct 88 ms 207812 KB Output is correct
11 Correct 93 ms 208264 KB Output is correct
12 Correct 98 ms 214444 KB Output is correct
13 Correct 99 ms 214668 KB Output is correct
14 Correct 87 ms 208076 KB Output is correct
15 Correct 87 ms 208172 KB Output is correct
16 Correct 86 ms 208032 KB Output is correct
17 Correct 91 ms 208852 KB Output is correct
18 Correct 89 ms 208172 KB Output is correct
19 Correct 87 ms 208076 KB Output is correct
20 Runtime error 185 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 87 ms 207744 KB Output is correct
2 Correct 87 ms 207764 KB Output is correct
3 Correct 86 ms 207788 KB Output is correct
4 Correct 87 ms 207812 KB Output is correct
5 Correct 86 ms 207824 KB Output is correct
6 Correct 98 ms 207720 KB Output is correct
7 Correct 90 ms 207788 KB Output is correct
8 Correct 86 ms 207820 KB Output is correct
9 Correct 91 ms 207808 KB Output is correct
10 Correct 87 ms 207820 KB Output is correct
11 Correct 97 ms 208236 KB Output is correct
12 Correct 96 ms 214560 KB Output is correct
13 Correct 96 ms 214612 KB Output is correct
14 Correct 87 ms 208152 KB Output is correct
15 Correct 100 ms 208080 KB Output is correct
16 Correct 92 ms 208100 KB Output is correct
17 Correct 90 ms 208924 KB Output is correct
18 Correct 99 ms 208184 KB Output is correct
19 Correct 88 ms 207984 KB Output is correct
20 Runtime error 177 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 89 ms 207780 KB Output is correct
2 Correct 86 ms 207760 KB Output is correct
3 Correct 93 ms 207740 KB Output is correct
4 Correct 89 ms 207768 KB Output is correct
5 Correct 88 ms 207780 KB Output is correct
6 Correct 90 ms 207712 KB Output is correct
7 Correct 88 ms 207708 KB Output is correct
8 Correct 86 ms 207820 KB Output is correct
9 Correct 86 ms 207768 KB Output is correct
10 Correct 87 ms 207932 KB Output is correct
11 Correct 94 ms 208320 KB Output is correct
12 Correct 107 ms 214568 KB Output is correct
13 Correct 97 ms 214676 KB Output is correct
14 Correct 89 ms 208148 KB Output is correct
15 Correct 87 ms 208100 KB Output is correct
16 Correct 87 ms 208060 KB Output is correct
17 Correct 96 ms 208928 KB Output is correct
18 Correct 92 ms 208188 KB Output is correct
19 Correct 87 ms 208008 KB Output is correct
20 Runtime error 185 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -