oj.uz

Submission #779977

# Submission time Handle Problem Language Result Execution time Memory
779977 2023-07-12T04:43:56 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 286 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];
bool seen[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();
        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 62 ms 152908 KB Output is correct
2 Correct 62 ms 153028 KB Output is correct
3 Correct 72 ms 153020 KB Output is correct
4 Correct 63 ms 152992 KB Output is correct
5 Correct 63 ms 153024 KB Output is correct
6 Correct 63 ms 152972 KB Output is correct
7 Correct 69 ms 153028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 153016 KB Output is correct
2 Correct 73 ms 152908 KB Output is correct
3 Correct 63 ms 153004 KB Output is correct
4 Correct 63 ms 153004 KB Output is correct
5 Correct 63 ms 152964 KB Output is correct
6 Correct 63 ms 153024 KB Output is correct
7 Correct 62 ms 153008 KB Output is correct
8 Correct 65 ms 152964 KB Output is correct
9 Correct 72 ms 153036 KB Output is correct
10 Correct 64 ms 153100 KB Output is correct
11 Correct 77 ms 153420 KB Output is correct
12 Correct 82 ms 159748 KB Output is correct
13 Correct 77 ms 159840 KB Output is correct
14 Correct 64 ms 153328 KB Output is correct
15 Correct 64 ms 153316 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 152916 KB Output is correct
2 Correct 63 ms 152996 KB Output is correct
3 Correct 65 ms 152964 KB Output is correct
4 Correct 67 ms 153004 KB Output is correct
5 Correct 64 ms 153028 KB Output is correct
6 Correct 70 ms 152944 KB Output is correct
7 Correct 64 ms 153028 KB Output is correct
8 Correct 64 ms 152988 KB Output is correct
9 Correct 65 ms 153040 KB Output is correct
10 Correct 63 ms 153112 KB Output is correct
11 Correct 65 ms 153456 KB Output is correct
12 Correct 75 ms 159700 KB Output is correct
13 Correct 73 ms 159828 KB Output is correct
14 Correct 71 ms 153364 KB Output is correct
15 Correct 64 ms 153360 KB Output is correct
16 Correct 64 ms 153316 KB Output is correct
17 Correct 67 ms 154024 KB Output is correct
18 Correct 64 ms 153288 KB Output is correct
19 Correct 64 ms 153276 KB Output is correct
20 Runtime error 286 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 62 ms 152908 KB Output is correct
2 Correct 63 ms 152936 KB Output is correct
3 Correct 65 ms 153140 KB Output is correct
4 Correct 71 ms 153024 KB Output is correct
5 Correct 64 ms 153020 KB Output is correct
6 Correct 63 ms 153020 KB Output is correct
7 Correct 63 ms 153000 KB Output is correct
8 Correct 64 ms 152936 KB Output is correct
9 Correct 67 ms 153144 KB Output is correct
10 Correct 73 ms 153008 KB Output is correct
11 Correct 66 ms 153448 KB Output is correct
12 Correct 86 ms 159688 KB Output is correct
13 Correct 74 ms 159768 KB Output is correct
14 Correct 76 ms 153328 KB Output is correct
15 Correct 67 ms 153292 KB Output is correct
16 Correct 67 ms 153284 KB Output is correct
17 Correct 71 ms 154008 KB Output is correct
18 Correct 65 ms 153300 KB Output is correct
19 Correct 66 ms 153220 KB Output is correct
20 Runtime error 239 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 63 ms 153024 KB Output is correct
2 Correct 64 ms 153000 KB Output is correct
3 Correct 62 ms 152956 KB Output is correct
4 Correct 63 ms 152968 KB Output is correct
5 Correct 63 ms 152908 KB Output is correct
6 Correct 63 ms 152948 KB Output is correct
7 Correct 65 ms 152944 KB Output is correct
8 Correct 65 ms 153012 KB Output is correct
9 Correct 64 ms 153044 KB Output is correct
10 Correct 63 ms 153132 KB Output is correct
11 Correct 65 ms 153548 KB Output is correct
12 Correct 82 ms 159860 KB Output is correct
13 Correct 73 ms 159820 KB Output is correct
14 Correct 64 ms 153332 KB Output is correct
15 Correct 64 ms 153276 KB Output is correct
16 Correct 67 ms 153312 KB Output is correct
17 Correct 76 ms 154112 KB Output is correct
18 Correct 65 ms 153372 KB Output is correct
19 Correct 64 ms 153196 KB Output is correct
20 Runtime error 260 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -