oj.uz

답안 #778954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778954 2023-07-11T05:13:21 Z horiiseun Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 226488 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;
map<pair<int, int>, int> mp;

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.count({x1, p1})) {
            mp.insert({{x1, p1}, idx++}); 
        }
        if (!mp.count({x2, p2})) {
            mp.insert({{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);

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 192004 KB Output is correct
2 Correct 80 ms 192092 KB Output is correct
3 Correct 78 ms 192012 KB Output is correct
4 Correct 78 ms 192032 KB Output is correct
5 Correct 80 ms 192020 KB Output is correct
6 Correct 88 ms 191980 KB Output is correct
7 Correct 84 ms 192044 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192052 KB Output is correct
2 Correct 80 ms 191988 KB Output is correct
3 Correct 78 ms 192052 KB Output is correct
4 Correct 89 ms 192088 KB Output is correct
5 Correct 85 ms 192096 KB Output is correct
6 Correct 79 ms 192096 KB Output is correct
7 Correct 78 ms 192100 KB Output is correct
8 Correct 78 ms 192088 KB Output is correct
9 Correct 79 ms 192096 KB Output is correct
10 Correct 81 ms 192224 KB Output is correct
11 Correct 93 ms 192828 KB Output is correct
12 Correct 168 ms 198752 KB Output is correct
13 Correct 177 ms 199008 KB Output is correct
14 Correct 94 ms 192808 KB Output is correct
15 Correct 94 ms 192820 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 192036 KB Output is correct
2 Correct 77 ms 192068 KB Output is correct
3 Correct 78 ms 192036 KB Output is correct
4 Correct 78 ms 192092 KB Output is correct
5 Correct 78 ms 192044 KB Output is correct
6 Correct 82 ms 192008 KB Output is correct
7 Correct 78 ms 192008 KB Output is correct
8 Correct 78 ms 192064 KB Output is correct
9 Correct 78 ms 192024 KB Output is correct
10 Correct 80 ms 192296 KB Output is correct
11 Correct 92 ms 192840 KB Output is correct
12 Correct 172 ms 198724 KB Output is correct
13 Correct 159 ms 199116 KB Output is correct
14 Correct 87 ms 192700 KB Output is correct
15 Correct 89 ms 192816 KB Output is correct
16 Correct 90 ms 192576 KB Output is correct
17 Correct 110 ms 194072 KB Output is correct
18 Correct 89 ms 192876 KB Output is correct
19 Correct 86 ms 192716 KB Output is correct
20 Execution timed out 1092 ms 226128 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 192076 KB Output is correct
2 Correct 80 ms 192028 KB Output is correct
3 Correct 80 ms 192036 KB Output is correct
4 Correct 80 ms 192080 KB Output is correct
5 Correct 79 ms 192088 KB Output is correct
6 Correct 92 ms 192056 KB Output is correct
7 Correct 81 ms 191992 KB Output is correct
8 Correct 79 ms 192040 KB Output is correct
9 Correct 78 ms 192008 KB Output is correct
10 Correct 82 ms 192196 KB Output is correct
11 Correct 103 ms 192820 KB Output is correct
12 Correct 171 ms 198816 KB Output is correct
13 Correct 160 ms 199044 KB Output is correct
14 Correct 88 ms 192716 KB Output is correct
15 Correct 86 ms 192792 KB Output is correct
16 Correct 93 ms 192588 KB Output is correct
17 Correct 130 ms 194020 KB Output is correct
18 Correct 94 ms 192972 KB Output is correct
19 Correct 86 ms 192704 KB Output is correct
20 Execution timed out 1086 ms 225804 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 192048 KB Output is correct
2 Correct 87 ms 191988 KB Output is correct
3 Correct 80 ms 192048 KB Output is correct
4 Correct 79 ms 192036 KB Output is correct
5 Correct 84 ms 192068 KB Output is correct
6 Correct 82 ms 192088 KB Output is correct
7 Correct 85 ms 192080 KB Output is correct
8 Correct 78 ms 192080 KB Output is correct
9 Correct 79 ms 192128 KB Output is correct
10 Correct 86 ms 192236 KB Output is correct
11 Correct 94 ms 192800 KB Output is correct
12 Correct 172 ms 198904 KB Output is correct
13 Correct 176 ms 199088 KB Output is correct
14 Correct 87 ms 192712 KB Output is correct
15 Correct 88 ms 192808 KB Output is correct
16 Correct 86 ms 192584 KB Output is correct
17 Correct 112 ms 194140 KB Output is correct
18 Correct 95 ms 192892 KB Output is correct
19 Correct 87 ms 192680 KB Output is correct
20 Execution timed out 1097 ms 226488 KB Time limit exceeded
21 Halted 0 ms 0 KB -