oj.uz

Submission #960678

# Submission time Handle Problem Language Result Execution time Memory
960678 2024-04-10T22:10:17 Z 3omar_ahmed Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 408 KB 
#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int n, m;
    cin >> n >> m;
    pair < int , int > first, second;
    vector < vector < int >> arr(1 + n);
    for(int i = 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        if(i == 0) {
            first = {a, b};
        } else if(i == 1) {
            second = {a, b};
        }
        arr[a].push_back(b);
    }
    int nodes = ((n + 1) * (n + 1)) + 5;
    vector < vector < pair < int , int >>> adj(nodes);
    for(int i = 0 ; i < n ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            int node = i * (n + 1) + j;
            if(i + j < n) {
                // cout << node << " " << (i + j) * (n + 1) + j << " 1" << endl;
                adj[node].push_back({(i + j) * (n + 1) + j, 1});
                // cout << node << " " << (i + j) * (n + 1) + n + 1 << " 1" << endl;
                adj[node].push_back({(i + j) * (n + 1) + n + 1, 1});
            }
            if(i - j >= 0) {
                // cout << node << " " << (i - j) * (n + 1) + j << " 1" << endl;
                adj[node].push_back({(i - j) * (n + 1) + j, 1});
                // cout << node << " " << (i - j) * (n + 1) + n + 1 << " 1" << endl;
                adj[node].push_back({(i - j) * (n + 1) + n + 1, 1});
            }
        }
        for(auto j : arr[i]) {
            // cout << (i * (n + 1)) + n + 1 << " " << (i * (n + 1)) + j << " " << 0 << endl;
            adj[i * (n + 1) + n + 1].push_back({i * (n + 1) + j, 0});
        }
    }
    int st = first.first * (n + 1) + first.second;
    vector < int > dis(nodes, 1e12);
    priority_queue < pair < int , int >> pq;
    pq.push({0, st});
    dis[st] = 0; 
    while(pq.size()) {
        auto top = pq.top();
        pq.pop();
        top.first *= -1;
        if(top.first != dis[top.second])
            continue;
        for(auto ch : adj[top.second]) {
            if(dis[ch.first] > top.first + ch.second) {
                dis[ch.first] = top.first + ch.second;
                pq.push({-dis[ch.first], ch.first});
            }
        }
    }
    int ans = 1e12;
    for(int i = 1 ; i <= n + 1 ; i++) {
        ans = min(ans, dis[second.first * (n + 1) + i]);
    }
    if(ans >= 1e10) ans = -1;
    cout << ans << endl;
    return 0 ;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 408 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -