Submission #552217

#	Time	Username	Problem	Language	Result	Execution time	Memory
552217		PiejanVDC	Sky Walking (IOI19_walk)	C++17	0 / 100	4094 ms	8516 KiB

walk

#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}});
            }
        }
    }
    return dist[{g,0}];
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43