Submission #294726

#	Time	Username	Problem	Language	Result	Execution time	Memory
294726		2qbingxuan	Sky Walking (IOI19_walk)	C++14	10 / 100	599 ms	1048580 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename H, typename ...T> void qqbx(const char *s, const H&h, T &&...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if constexpr(sizeof...(T)) qqbx(++s, args...);
}
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v),end(v)

using namespace std;


struct Dijkstra {
    vector<vector<pair<int,int>>> g;
    vector<long long> dis;
    Dijkstra(int n) : g(n), dis(n) {}
    void addEdge(int a, int b, int c) {
        g[a].pb(c, b);
        g[b].pb(c, a);
    }
    long long calc(int s, int t) {
        fill(dis.begin(), dis.end(), -1);
        priority_queue<pair<long long,int>> pq;
        pq.push({dis[s]=0, s});
        while(!pq.empty()) {
            auto [d, i] = pq.top(); pq.pop();
            if(d != dis[i]) continue;
            for(auto [c, j]: g[i]) {
                if(dis[j] == -1 || dis[j] > d + c) {
                    pq.push({dis[j]=c+d, j});
                }
            }
        }
        return dis[t];
    }
};

int getId(int i, int y) {
    static int tot;
    static map<pair<int,int>, int> mp;
    if(mp.count({i,y})) return mp[{i,y}];
    return mp[{i,y}] = tot++;
}
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) {
    int n = x.size();
    int m = l.size();
    Dijkstra dij(n*m);
    vector<vector<pair<int,int>>> junc(n);
    for(int i = 0; i < m; i++) {
        int last = -1;
        for(int j = l[i]; j <= r[i]; j++) {
            if(h[j] < y[i]) continue;
            if(last != -1) dij.addEdge(getId(last, y[i]), getId(j, y[i]), x[j]-x[last]);
            last = j;
            junc[j].pb(y[i], getId(j, y[i]));
        }
    }
    for(int i = 0; i < n; i++) junc[i].pb(0, getId(i, 0));
    for(int i = 0; i < n; i++) {
        sort(all(junc[i]));
        for(int j = 0; j+1 < junc[i].size(); j++) {
            dij.addEdge(junc[i][j].second, junc[i][j+1].second, junc[i][j+1].first - junc[i][j].first);
        }
    }
    return dij.calc(getId(s, 0), getId(g, 0));
}

Compilation message (stderr)

walk.cpp: In member function 'long long int Dijkstra::calc(int, int)':
walk.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |             auto [d, i] = pq.top(); pq.pop();
      |                  ^
walk.cpp:36:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |             for(auto [c, j]: g[i]) {
      |                      ^
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:69:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int j = 0; j+1 < junc[i].size(); j++) {
      |                        ~~~~^~~~~~~~~~~~~~~~

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