oj.uz

Submission #1103002

# Submission time Handle Problem Language Result Execution time Memory
1103002 2024-10-19T10:40:39 Z stefdasca OBELISK (NOI14_obelisk) C++14
0 / 25
 1000 ms 262144 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
#define ll long long
#define fff(i, a, b) for(int i = a; i < b; i++)
#define fffm(i, a, b) for(int i = a; i > b; i--)
#define ff(a, c) for(auto a: c)
#define x first
#define y second
 
#define MAXK 505
ll k, m;
pair<ll, ll> strt, nd;
vector<pair<ll, ll>> floors[MAXK];
ll dist(pair<ll, ll> p1, pair<ll, ll> p2){
    if (m == 1) return abs(p1.x-p2.x) + abs(p1.y-p2.y);
    return (abs(p1.x-p2.x) % (m+1)) + (abs(p1.y-p2.y) % (m+1)) + 2*(max(abs(p1.x-p2.x)/(m+1), (p1.x-p2.x) ? 1ll:0ll)) + 2*(max(abs(p1.y-p2.y)/(m+1), (p1.y-p2.y) ? 1ll:0ll));
}
 
priority_queue<pair<pair<ll, int>, pair<ll, ll>>> q;
long long shp[505];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> k >> m;
    cin >> strt.x >> strt.y >> nd.x >> nd.y;
    fffm(i, k-1, 0){
        ll ln; cin >> ln;
        fff(j, 0, ln){
            pair<ll, ll> a;
            cin >> a.x >> a.y;
            floors[i].push_back(a);
        }
    }
    q.push({{0, k}, strt});
    ll ans = INT64_MAX;
    while(q.size()){
        auto [a, pt] = q.top(); q.pop();
        auto [dst, flr] = a;
        if (dst > shp[flr]) {
            continue;
        }
        if (flr == 1){
            ans = min(ans, -dst + dist(pt, nd));
        }else{
            ff(p2, floors[flr-1]){
                ll d2 = dst - dist(pt, p2);
                if (d2 < shp[flr-1]) {
                    q.push({{d2, flr-1}, p2});
                }
            }
        }
    }
    cout << ans << endl;
}

Compilation message

obelisk.cpp: In function 'int main()':
obelisk.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto [a, pt] = q.top(); q.pop();
      |              ^
obelisk.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         auto [dst, flr] = a;
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 35248 KB Output is correct
2 Execution timed out 1071 ms 68240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 265 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 256 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -