Submission #416341

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416341	2021-06-02T10:30:40 Z	idk321	Sky Walking (IOI19_walk)	C++17	Compilation error	0 ms	0 KB

walk

#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];
}
#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++)
      |                      ~~~^~~~~~~~~~
walk.cpp: At global scope:
walk.cpp:130:11: error: redefinition of 'const int M'
  130 | const int M = 2000005;
      |           ^
walk.cpp:8:11: note: 'const int M' previously defined here
    8 | const int M = 2000005;
      |           ^
walk.cpp:131:11: error: redefinition of 'const int N'
  131 | const int N = 100005;
      |           ^
walk.cpp:9:11: note: 'const int N' previously defined here
    9 | const int N = 100005;
      |           ^
walk.cpp:132:10: error: redefinition of 'const ll INF'
  132 | const ll INF = 2000000000000000000LL;
      |          ^~~
walk.cpp:10:10: note: 'const ll INF' previously defined here
   10 | const ll INF = 2000000000000000000LL;
      |          ^~~
walk.cpp:133:23: error: redefinition of 'std::vector<std::array<int, 2> > adj [2000005]'
  133 | vector<array<int, 2>> adj[M];
      |                       ^~~
walk.cpp:11:23: note: 'std::vector<std::array<int, 2> > adj [2000005]' previously declared here
   11 | vector<array<int, 2>> adj[M];
      |                       ^~~
walk.cpp:134:23: error: redefinition of 'std::vector<std::array<int, 2> > isAt [100005]'
  134 | vector<array<int, 2>> isAt[N];
      |                       ^~~~
walk.cpp:12:23: note: 'std::vector<std::array<int, 2> > isAt [100005]' previously declared here
   12 | vector<array<int, 2>> isAt[N];
      |                       ^~~~
walk.cpp:136:5: error: redefinition of 'int cnode'
  136 | int cnode = 0;
      |     ^~~~~
walk.cpp:14:5: note: 'int cnode' previously defined here
   14 | int cnode = 0;
      |     ^~~~~
walk.cpp:141:8: error: redefinition of 'struct Comparator'
  141 | struct Comparator
      |        ^~~~~~~~~~
walk.cpp:19:8: note: previous definition of 'struct Comparator'
   19 | struct Comparator
      |        ^~~~~~~~~~
walk.cpp:150:11: error: redefinition of 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)'
  150 | 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) {
      |           ^~~~~~~~~~~~
walk.cpp:28:11: note: 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)' previously defined here
   28 | 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) {
      |           ^~~~~~~~~~~~
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:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (int i = 0; i < l.size(); i++)
      |                     ~~^~~~~~~~~~
walk.cpp:179:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for (int i = 0; i < x.size(); i++) ok.insert(i);
      |                     ~~^~~~~~~~~~
walk.cpp:181:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for (int ci = 0; ci < l.size(); ci++)
      |                      ~~~^~~~~~~~~~