oj.uz

답안 #779978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779978 2023-07-12T04:45:02 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 269 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);
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 153004 KB Output is correct
2 Correct 63 ms 152952 KB Output is correct
3 Correct 62 ms 152976 KB Output is correct
4 Correct 66 ms 152948 KB Output is correct
5 Correct 62 ms 153020 KB Output is correct
6 Correct 63 ms 152936 KB Output is correct
7 Correct 62 ms 152908 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 153044 KB Output is correct
2 Correct 63 ms 153012 KB Output is correct
3 Correct 62 ms 153024 KB Output is correct
4 Correct 64 ms 152996 KB Output is correct
5 Correct 72 ms 152980 KB Output is correct
6 Correct 64 ms 152904 KB Output is correct
7 Correct 64 ms 152940 KB Output is correct
8 Correct 64 ms 152964 KB Output is correct
9 Correct 64 ms 152932 KB Output is correct
10 Correct 64 ms 153088 KB Output is correct
11 Correct 70 ms 153392 KB Output is correct
12 Correct 72 ms 158992 KB Output is correct
13 Correct 73 ms 159308 KB Output is correct
14 Correct 66 ms 153344 KB Output is correct
15 Correct 65 ms 153356 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 152952 KB Output is correct
2 Correct 68 ms 152928 KB Output is correct
3 Correct 63 ms 152996 KB Output is correct
4 Correct 63 ms 152924 KB Output is correct
5 Correct 62 ms 153028 KB Output is correct
6 Correct 63 ms 152960 KB Output is correct
7 Correct 72 ms 152932 KB Output is correct
8 Correct 62 ms 153024 KB Output is correct
9 Correct 63 ms 153020 KB Output is correct
10 Correct 64 ms 153104 KB Output is correct
11 Correct 65 ms 153404 KB Output is correct
12 Correct 70 ms 159068 KB Output is correct
13 Correct 76 ms 159276 KB Output is correct
14 Correct 64 ms 153348 KB Output is correct
15 Correct 64 ms 153288 KB Output is correct
16 Correct 65 ms 153280 KB Output is correct
17 Correct 69 ms 154112 KB Output is correct
18 Correct 63 ms 153368 KB Output is correct
19 Correct 64 ms 153148 KB Output is correct
20 Runtime error 241 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 152972 KB Output is correct
2 Correct 62 ms 152960 KB Output is correct
3 Correct 63 ms 152908 KB Output is correct
4 Correct 62 ms 152916 KB Output is correct
5 Correct 65 ms 153000 KB Output is correct
6 Correct 63 ms 152908 KB Output is correct
7 Correct 63 ms 153000 KB Output is correct
8 Correct 65 ms 153028 KB Output is correct
9 Correct 63 ms 152944 KB Output is correct
10 Correct 63 ms 153128 KB Output is correct
11 Correct 67 ms 153544 KB Output is correct
12 Correct 71 ms 159076 KB Output is correct
13 Correct 82 ms 159236 KB Output is correct
14 Correct 66 ms 153340 KB Output is correct
15 Correct 66 ms 153308 KB Output is correct
16 Correct 63 ms 153164 KB Output is correct
17 Correct 70 ms 154008 KB Output is correct
18 Correct 66 ms 153320 KB Output is correct
19 Correct 66 ms 153272 KB Output is correct
20 Runtime error 269 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 152964 KB Output is correct
2 Correct 64 ms 152944 KB Output is correct
3 Correct 63 ms 152908 KB Output is correct
4 Correct 63 ms 152940 KB Output is correct
5 Correct 62 ms 152940 KB Output is correct
6 Correct 66 ms 153000 KB Output is correct
7 Correct 63 ms 153028 KB Output is correct
8 Correct 64 ms 153028 KB Output is correct
9 Correct 69 ms 152944 KB Output is correct
10 Correct 66 ms 153128 KB Output is correct
11 Correct 65 ms 153420 KB Output is correct
12 Correct 71 ms 159052 KB Output is correct
13 Correct 70 ms 159308 KB Output is correct
14 Correct 77 ms 153360 KB Output is correct
15 Correct 64 ms 153308 KB Output is correct
16 Correct 63 ms 153240 KB Output is correct
17 Correct 67 ms 154104 KB Output is correct
18 Correct 75 ms 153252 KB Output is correct
19 Correct 66 ms 153224 KB Output is correct
20 Runtime error 252 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -