oj.uz

Submission #552218

# Submission time Handle Problem Language Result Execution time Memory
552218 2022-04-22T19:09:46 Z PiejanVDC Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 8592 KB 
#include<bits/stdc++.h>
using namespace std;

#include "walk.h"

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    const long long n = (long long)x.size();
    const long long m = (long long)l.size();

    vector<set<long long>>v(n);

    v[g].insert(0);
    v[s].insert(0);

    set<pair<long long,pair<long long,long long>>>connected;

    for(long long i = 0 ; i < m ; i++) {
        for(long long ii = l[i] ; ii <= r[i] ; ii++) {
            if(ii < r[i])
                connected.insert({y[i], {ii, ii+1}});
            v[ii].insert(y[i]);
        }
    }

    map<pair<long long,long long>,long long>dist;

    dist[{s,0}] = 0;

    priority_queue<pair<long long,pair<long long,long long>>>pq;
    pq.push({0,{s,0}});

    while(!pq.empty()) {
        auto node = pq.top();
        pq.pop();
        auto [i,y] = node.second;
        if(i > 0 && v[i-1].count(y) && connected.count({y, {i-1,i}})) {
            if((!dist.count({i-1,y}) || dist[{i,y}] + i - x[i-1] < dist[{i-1,y}])) {
                dist[{i-1,y}] = dist[{i,y}] + x[i] - x[i-1];
                pq.push({-dist[{i-1,y}], {i-1, y}});
            }
        }
        if(i < n-1 && v[i+1].count(y) && connected.count({y, {i,i+1}})) {
            if((!dist.count({i+1,y}) || dist[{i,y}] + x[i+1] - i < dist[{i+1,y}])) {
                dist[{i+1,y}] = dist[{i,y}] + x[i+1] - x[i];
                pq.push({-dist[{i+1,y}], {i+1, y}});
            }
        }
        for(auto it = v[i].begin() ; it != v[i].end() ; it++) {
            long long yy = *it;
            if(yy > h[i] || y > h[i])
                break;
            if(!dist[{i,yy}] || dist[{i,y}] + abs(y - yy) < dist[{i,yy}]) {
                dist[{i,yy}] = dist[{i,y}] + abs(y - yy);
                pq.push({-dist[{i,yy}], {i, yy}});
            }
        }
    }
    if(!dist.count({g,0}))
        return -1;
    return dist[{g,0}];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 8592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 8592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -