Submission #798688

#	Time	Username	Problem	Language	Result	Execution time	Memory
798688		resting	Sky Walking (IOI19_walk)	C++17	0 / 100	10 ms	2232 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

// 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) {

// }

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) {  // basically dijkstra
    int n = x.size(), m = l.size();
    map<pair<int, int>, ll> dist;
    set<pair<ll, pair<int, int>>> ss;
    ss.insert({ 1, {s, 0} });
    while (ss.size()) {
        auto t = *ss.begin();
        ss.erase(ss.begin());
        int tim = t.first, xx = t.second.first, yy = t.second.second;
        if (dist[t.second]) break;
        dist[t.second] = t.first;
        for (int i = 0; i < m; i++) {
            if (y[i] == yy && l[i] <= xx && r[i] > xx) ss.insert({ tim + x[xx + 1] - x[xx], {xx + 1, yy} });
            if (y[i] == yy && l[i] < xx && r[i] >= xx) ss.insert({ tim + x[xx] - x[xx - 1], {xx - 1, yy} });
            if (l[i] <= xx && r[i] >= xx && h[xx] >= y[i]) ss.insert({ tim + abs(y[i] - yy), {xx, y[i]} });
        }
        ss.insert({tim + yy, {xx, 0} });
    }
    return dist[{g, 0}];
}

// int main() {

// }

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:12:9: warning: unused variable 'n' [-Wunused-variable]
   12 |     int n = x.size(), m = l.size();
      |         ^

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