oj.uz

Submission #294726

# Submission time Handle Problem Language Result Execution time Memory
294726 2020-09-09T08:51:46 Z 2qbingxuan Sky Walking (IOI19_walk) C++14
10 / 100
 599 ms 1048580 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 12 ms 512 KB Output is correct
6 Correct 11 ms 512 KB Output is correct
7 Correct 6 ms 548 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 22 ms 512 KB Output is correct
11 Correct 1 ms 372 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 372 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 18 ms 640 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Runtime error 54 ms 7672 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 599 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 599 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 12 ms 512 KB Output is correct
6 Correct 11 ms 512 KB Output is correct
7 Correct 6 ms 548 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 22 ms 512 KB Output is correct
11 Correct 1 ms 372 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 372 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 18 ms 640 KB Output is correct
18 Correct 1 ms 288 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Runtime error 54 ms 7672 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -