oj.uz

Submission #779981

# Submission time Handle Problem Language Result Execution time Memory
779981 2023-07-12T04:46:27 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 234 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[6000005];
vector<pair<int, int>> adj[6000005], 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 + 6000005, 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 70 ms 180384 KB Output is correct
2 Correct 70 ms 180364 KB Output is correct
3 Correct 70 ms 180416 KB Output is correct
4 Correct 69 ms 180304 KB Output is correct
5 Correct 73 ms 180428 KB Output is correct
6 Correct 70 ms 180320 KB Output is correct
7 Correct 70 ms 180316 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 180296 KB Output is correct
2 Correct 69 ms 180352 KB Output is correct
3 Correct 68 ms 180412 KB Output is correct
4 Correct 69 ms 180344 KB Output is correct
5 Correct 73 ms 180352 KB Output is correct
6 Correct 79 ms 180404 KB Output is correct
7 Correct 69 ms 180316 KB Output is correct
8 Correct 75 ms 180416 KB Output is correct
9 Correct 76 ms 180384 KB Output is correct
10 Correct 71 ms 180480 KB Output is correct
11 Correct 80 ms 180744 KB Output is correct
12 Correct 79 ms 186444 KB Output is correct
13 Correct 78 ms 186708 KB Output is correct
14 Correct 87 ms 180640 KB Output is correct
15 Correct 73 ms 180696 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 180324 KB Output is correct
2 Correct 78 ms 180408 KB Output is correct
3 Correct 77 ms 180336 KB Output is correct
4 Correct 79 ms 180300 KB Output is correct
5 Correct 76 ms 180376 KB Output is correct
6 Correct 77 ms 180340 KB Output is correct
7 Correct 76 ms 180336 KB Output is correct
8 Correct 80 ms 180400 KB Output is correct
9 Correct 78 ms 180428 KB Output is correct
10 Correct 79 ms 180460 KB Output is correct
11 Correct 77 ms 180820 KB Output is correct
12 Correct 84 ms 186416 KB Output is correct
13 Correct 88 ms 186700 KB Output is correct
14 Correct 84 ms 180720 KB Output is correct
15 Correct 89 ms 180728 KB Output is correct
16 Correct 78 ms 180552 KB Output is correct
17 Correct 87 ms 181500 KB Output is correct
18 Correct 78 ms 180664 KB Output is correct
19 Correct 77 ms 180556 KB Output is correct
20 Runtime error 193 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 77 ms 180376 KB Output is correct
2 Correct 90 ms 180312 KB Output is correct
3 Correct 77 ms 180416 KB Output is correct
4 Correct 76 ms 180384 KB Output is correct
5 Correct 89 ms 180328 KB Output is correct
6 Correct 78 ms 180300 KB Output is correct
7 Correct 76 ms 180368 KB Output is correct
8 Correct 83 ms 180324 KB Output is correct
9 Correct 77 ms 180392 KB Output is correct
10 Correct 90 ms 180452 KB Output is correct
11 Correct 78 ms 180836 KB Output is correct
12 Correct 84 ms 186484 KB Output is correct
13 Correct 86 ms 186704 KB Output is correct
14 Correct 77 ms 180644 KB Output is correct
15 Correct 80 ms 180632 KB Output is correct
16 Correct 78 ms 180672 KB Output is correct
17 Correct 82 ms 181408 KB Output is correct
18 Correct 80 ms 180648 KB Output is correct
19 Correct 77 ms 180556 KB Output is correct
20 Runtime error 234 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 78 ms 180352 KB Output is correct
2 Correct 91 ms 180300 KB Output is correct
3 Correct 78 ms 180360 KB Output is correct
4 Correct 82 ms 180412 KB Output is correct
5 Correct 75 ms 180304 KB Output is correct
6 Correct 75 ms 180288 KB Output is correct
7 Correct 77 ms 180332 KB Output is correct
8 Correct 75 ms 180396 KB Output is correct
9 Correct 76 ms 180428 KB Output is correct
10 Correct 81 ms 180548 KB Output is correct
11 Correct 77 ms 180816 KB Output is correct
12 Correct 84 ms 186388 KB Output is correct
13 Correct 85 ms 186608 KB Output is correct
14 Correct 90 ms 180680 KB Output is correct
15 Correct 78 ms 180708 KB Output is correct
16 Correct 79 ms 180700 KB Output is correct
17 Correct 81 ms 181488 KB Output is correct
18 Correct 78 ms 180676 KB Output is correct
19 Correct 79 ms 180616 KB Output is correct
20 Runtime error 203 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -