Submission #798688

# Submission time Handle Problem Language Result Execution time Memory
798688 2023-07-30T23:40:48 Z resting Sky Walking (IOI19_walk) C++17
0 / 100
10 ms 2232 KB
#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

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();
      |         ^
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2232 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2232 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -