oj.uz

Submission #417835

# Submission time Handle Problem Language Result Execution time Memory
417835 2021-06-04T11:26:36 Z idk321 Sky Walking (IOI19_walk) C++17
0 / 100
 246 ms 82112 KB 

#include "walk.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int M = 2000005;
const int N = 100005;
const ll INF = 2000000000000000000LL;
vector<array<int, 2>> adj[M];
vector<array<int, 2>> isAt[N];

int cnode = 0;


///usr/include/c++/10/bits/stl_heap.h|209|error: ‘bool Comparator::operator()(const std::__debug::array<long long int, 2>&, const std::__debug::array<long long int, 2>&) const’ is private within this context|

struct Comparator
{

    bool operator() (const array<ll, 2>& ar1, const array<ll, 2>& ar2) const
    {
        return tie(ar1[1], ar1[0]) > tie(ar2[1], ar2[0]);
    }
};

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

    if (s > g)
    {
        swap(s, g);
    }

    int snode = -1;
    int gnode = -1;
    for (int i = 0; i < x.size(); i++)
    {
        isAt[i].push_back({cnode, 0});
        if (i == s)
        {
            snode = cnode;
        }
        if (i == g)
        {
            gnode = cnode;
        }
        cnode++;
    }



    vector<array<int, 2>> byHeight;
    for (int i = 0; i < l.size(); i++)
    {
        byHeight.push_back({y[i], i});
    }
    sort(byHeight.begin(), byHeight.end());



    for (int ci = 0; ci < l.size(); ci++)
    {
        int i = byHeight[ci][1];
        int prev = -1;

        vector<int> build;
        build.push_back(l[i]);
        if (l[i]< s && s < r[i] && y[i] <= h[s]) build.push_back(s);
        if (l[i]< g && g < r[i] && y[i] <= h[g]) build.push_back(g);
        build.push_back(r[i]);
        for (int cur : build)
        {
            adj[cnode].push_back({isAt[cur].back()[0], y[i] - isAt[cur].back()[1]});
            adj[isAt[cur].back()[0]].push_back({cnode, y[i] - isAt[cur].back()[1]});
            isAt[cur].push_back({cnode, y[i]});

            if (prev != -1)
            {
                adj[cnode].push_back({cnode - 1, x[cur] - x[prev]});
                adj[cnode - 1].push_back({cnode, x[cur] - x[prev]});
            }


            prev = cur;
            cnode++;
        }
    }

    priority_queue<array<ll, 2>, vector<array<ll, 2>>, Comparator> pq;

    pq.push({snode, 0});

    vector<ll> dist(M, INF);
    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        if (dist[cur[0]] != INF) continue;
        dist[cur[0]] = cur[1];



        for (auto next : adj[cur[0]])
        {
            if (dist[next[0]] == INF)
            {

                pq.push({next[0], next[1] + cur[1]});
            }
        }
    }



    if (dist[gnode] == INF) return -1;
    return dist[gnode];
}

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:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int ci = 0; ci < l.size(); ci++)
      |                      ~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65224 KB Output is correct
2 Incorrect 36 ms 65216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65188 KB Output is correct
2 Incorrect 37 ms 65200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 73876 KB Output is correct
2 Incorrect 246 ms 82112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 73876 KB Output is correct
2 Incorrect 246 ms 82112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65224 KB Output is correct
2 Incorrect 36 ms 65216 KB Output isn't correct
3 Halted 0 ms 0 KB -