oj.uz

Submission #1102777

# Submission time Handle Problem Language Result Execution time Memory
1102777 2024-10-18T20:53:30 Z jnjwnwnw OBELISK (NOI14_obelisk) C++17
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;
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 (flr == 1){
            ans = min(ans, -dst + dist(pt, nd));
        }else{
            ff(p2, floors[flr-1]){
                ll d2 = dst - dist(pt, p2);
                q.push({{d2, flr-1}, p2});
            }
        }
    }
    cout << ans << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 35244 KB Output is correct
2 Execution timed out 1064 ms 68260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 259 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 287 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 275 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -