oj.uz

Submission #416342

# Submission time Handle Problem Language Result Execution time Memory
416342 2021-06-02T10:31:32 Z idk321 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 1048580 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])
            {
                for (auto ar : isAt[j])
                {
                    adj[cnode].push_back({ar[0], abs(ar[1] - y[i])});
                    adj[ar[0]].push_back({cnode, abs(ar[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 36 ms 65204 KB Output is correct
2 Correct 37 ms 65200 KB Output is correct
3 Correct 38 ms 65236 KB Output is correct
4 Correct 38 ms 65220 KB Output is correct
5 Correct 37 ms 65436 KB Output is correct
6 Correct 38 ms 65284 KB Output is correct
7 Correct 37 ms 65308 KB Output is correct
8 Correct 36 ms 65312 KB Output is correct
9 Correct 41 ms 65320 KB Output is correct
10 Correct 38 ms 65476 KB Output is correct
11 Correct 39 ms 65228 KB Output is correct
12 Correct 37 ms 65260 KB Output is correct
13 Correct 37 ms 65184 KB Output is correct
14 Correct 41 ms 65216 KB Output is correct
15 Correct 36 ms 65160 KB Output is correct
16 Correct 36 ms 65228 KB Output is correct
17 Correct 38 ms 65508 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65156 KB Output is correct
2 Correct 36 ms 65176 KB Output is correct
3 Execution timed out 4107 ms 762872 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 86488 KB Output is correct
2 Runtime error 3275 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 86488 KB Output is correct
2 Runtime error 3275 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65204 KB Output is correct
2 Correct 37 ms 65200 KB Output is correct
3 Correct 38 ms 65236 KB Output is correct
4 Correct 38 ms 65220 KB Output is correct
5 Correct 37 ms 65436 KB Output is correct
6 Correct 38 ms 65284 KB Output is correct
7 Correct 37 ms 65308 KB Output is correct
8 Correct 36 ms 65312 KB Output is correct
9 Correct 41 ms 65320 KB Output is correct
10 Correct 38 ms 65476 KB Output is correct
11 Correct 39 ms 65228 KB Output is correct
12 Correct 37 ms 65260 KB Output is correct
13 Correct 37 ms 65184 KB Output is correct
14 Correct 41 ms 65216 KB Output is correct
15 Correct 36 ms 65160 KB Output is correct
16 Correct 36 ms 65228 KB Output is correct
17 Correct 38 ms 65508 KB Output is correct
18 Correct 42 ms 65156 KB Output is correct
19 Correct 36 ms 65176 KB Output is correct
20 Execution timed out 4107 ms 762872 KB Time limit exceeded
21 Halted 0 ms 0 KB -