oj.uz

Submission #416367

# Submission time Handle Problem Language Result Execution time Memory
416367 2021-06-02T10:38:07 Z idk321 Sky Walking (IOI19_walk) C++17
24 / 100
 1151 ms 347064 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) {

    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());

    set<int> ok;

    for (int i = 0; i < x.size(); i++) ok.insert(i);

    for (int ci = 0; ci < l.size(); ci++)
    {
        int i = byHeight[ci][1];
        int prev = -1;
        for (auto it = ok.lower_bound(l[i]); it != ok.end() && *it <= r[i]; )
        {
            int j = *it;
            if (h[j] >= y[i])
            {

                adj[cnode].push_back({isAt[j].back()[0], abs(isAt[j].back()[1] - y[i])});
                adj[isAt[j].back()[0]].push_back({cnode, abs(isAt[j].back()[1] - y[i])});


                isAt[j].push_back({cnode, y[i]});
                if (prev != -1)
                {
                    adj[cnode].push_back({cnode - 1, x[j] - x[prev]});
                    adj[cnode - 1].push_back({cnode, x[j] - x[prev]});
                }
                prev = j;
                cnode++;
                it++;
            } else
            {
                it = ok.erase(it);
            }
        }
    }

    set<array<ll, 2>, Comparator> sett;

    sett.insert({snode, 0});

    vector<ll> dist(M, INF);
    dist[snode] = 0;
    while (!sett.empty())
    {
        auto cur = *sett.begin();
        sett.erase(sett.begin());



        for (auto next : adj[cur[0]])
        {
            if (cur[1] + next[1] < dist[next[0]])
            {
                if (dist[next[0]] != INF)
                {
                    sett.erase({next[0], dist[next[0]]});
                }
                dist[next[0]] = cur[1] + next[1];
                sett.insert({next[0], cur[1] + next[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:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < x.size(); i++) ok.insert(i);
      |                     ~~^~~~~~~~~~
walk.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int ci = 0; ci < l.size(); ci++)
      |                      ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65260 KB Output is correct
2 Correct 44 ms 65180 KB Output is correct
3 Correct 44 ms 65224 KB Output is correct
4 Correct 45 ms 65168 KB Output is correct
5 Correct 47 ms 65292 KB Output is correct
6 Correct 44 ms 65200 KB Output is correct
7 Correct 41 ms 65228 KB Output is correct
8 Correct 40 ms 65212 KB Output is correct
9 Correct 40 ms 65224 KB Output is correct
10 Correct 42 ms 65216 KB Output is correct
11 Correct 45 ms 65192 KB Output is correct
12 Correct 45 ms 65208 KB Output is correct
13 Correct 41 ms 65180 KB Output is correct
14 Correct 41 ms 65288 KB Output is correct
15 Correct 44 ms 65144 KB Output is correct
16 Correct 40 ms 65268 KB Output is correct
17 Correct 41 ms 65232 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 65160 KB Output is correct
2 Correct 42 ms 65216 KB Output is correct
3 Correct 701 ms 112924 KB Output is correct
4 Correct 996 ms 123772 KB Output is correct
5 Correct 561 ms 113568 KB Output is correct
6 Correct 525 ms 108220 KB Output is correct
7 Correct 518 ms 113508 KB Output is correct
8 Correct 835 ms 124068 KB Output is correct
9 Correct 654 ms 113260 KB Output is correct
10 Correct 1151 ms 139228 KB Output is correct
11 Correct 565 ms 94804 KB Output is correct
12 Correct 486 ms 95032 KB Output is correct
13 Correct 1092 ms 133940 KB Output is correct
14 Correct 272 ms 88256 KB Output is correct
15 Correct 350 ms 91968 KB Output is correct
16 Correct 358 ms 91780 KB Output is correct
17 Correct 417 ms 90680 KB Output is correct
18 Correct 216 ms 92860 KB Output is correct
19 Correct 48 ms 66320 KB Output is correct
20 Correct 123 ms 76948 KB Output is correct
21 Correct 379 ms 90360 KB Output is correct
22 Correct 456 ms 96604 KB Output is correct
23 Correct 298 ms 96000 KB Output is correct
24 Correct 394 ms 93848 KB Output is correct
25 Correct 412 ms 90732 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 75008 KB Output is correct
2 Runtime error 679 ms 347064 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 75008 KB Output is correct
2 Runtime error 679 ms 347064 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65260 KB Output is correct
2 Correct 44 ms 65180 KB Output is correct
3 Correct 44 ms 65224 KB Output is correct
4 Correct 45 ms 65168 KB Output is correct
5 Correct 47 ms 65292 KB Output is correct
6 Correct 44 ms 65200 KB Output is correct
7 Correct 41 ms 65228 KB Output is correct
8 Correct 40 ms 65212 KB Output is correct
9 Correct 40 ms 65224 KB Output is correct
10 Correct 42 ms 65216 KB Output is correct
11 Correct 45 ms 65192 KB Output is correct
12 Correct 45 ms 65208 KB Output is correct
13 Correct 41 ms 65180 KB Output is correct
14 Correct 41 ms 65288 KB Output is correct
15 Correct 44 ms 65144 KB Output is correct
16 Correct 40 ms 65268 KB Output is correct
17 Correct 41 ms 65232 KB Output is correct
18 Correct 40 ms 65160 KB Output is correct
19 Correct 42 ms 65216 KB Output is correct
20 Correct 701 ms 112924 KB Output is correct
21 Correct 996 ms 123772 KB Output is correct
22 Correct 561 ms 113568 KB Output is correct
23 Correct 525 ms 108220 KB Output is correct
24 Correct 518 ms 113508 KB Output is correct
25 Correct 835 ms 124068 KB Output is correct
26 Correct 654 ms 113260 KB Output is correct
27 Correct 1151 ms 139228 KB Output is correct
28 Correct 565 ms 94804 KB Output is correct
29 Correct 486 ms 95032 KB Output is correct
30 Correct 1092 ms 133940 KB Output is correct
31 Correct 272 ms 88256 KB Output is correct
32 Correct 350 ms 91968 KB Output is correct
33 Correct 358 ms 91780 KB Output is correct
34 Correct 417 ms 90680 KB Output is correct
35 Correct 216 ms 92860 KB Output is correct
36 Correct 48 ms 66320 KB Output is correct
37 Correct 123 ms 76948 KB Output is correct
38 Correct 379 ms 90360 KB Output is correct
39 Correct 456 ms 96604 KB Output is correct
40 Correct 298 ms 96000 KB Output is correct
41 Correct 394 ms 93848 KB Output is correct
42 Correct 412 ms 90732 KB Output is correct
43 Correct 143 ms 75008 KB Output is correct
44 Runtime error 679 ms 347064 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -