Submission #296230

#	Time	Username	Problem	Language	Result	Execution time	Memory
296230		SamAnd	Sky Walking (IOI19_walk)	C++17	10 / 100	4089 ms	1048580 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, m;

map<int, vector<int> > g[N];
set<pair<int, int> > c;
set<int> s[N];

struct ban
{
    pair<int, int> u;
    ll d;
    ban(){}
    ban(pair<int, int> u, ll d)
    {
        this->u = u;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

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 F)
{
    n = sz(x);
    m = sz(y);
    for (int i = 0; i < m; ++i)
    {
        for (int j = l[i]; j <= r[i]; ++j)
            s[j].insert(y[i]);
        for (int j = l[i]; j < r[i]; ++j)
        {
            if (h[j] < y[i])
                continue;
            for (int k = j + 1; k <= r[i]; ++k)
            {
                if (h[k] < y[i])
                    continue;
                g[j][y[i]].push_back(k);
                g[k][y[i]].push_back(j);
            }
        }
    }
    s[S].insert(0);
    s[F].insert(0);

    priority_queue<ban> q;
    q.push(ban(m_p(S, 0), 0));
    while (1)
    {
        ban t;
        do
        {
            if (q.empty())
                return -1;
            t = q.top();
            q.pop();
        } while (c.find(t.u) != c.end());
        c.insert(t.u);
        if (t.u == m_p(F, 0))
            return t.d;
        for (int i = 0; i < g[t.u.fi][t.u.se].size(); ++i)
        {
            ban h = ban(m_p(g[t.u.fi][t.u.se][i], t.u.se), t.d);
            h.d += abs(x[t.u.fi] - x[h.u.fi]);
            q.push(h);
        }
        auto it = s[t.u.fi].find(t.u.se);
        if (it != s[t.u.fi].end())
        {
            ++it;
            ban h = ban(m_p(t.u.fi, *it), t.d + *it - t.u.se);
            q.push(h);
            --it;
        }
        if (it != s[t.u.fi].begin())
        {
            --it;
            ban h = ban(m_p(t.u.fi, *it), t.d + t.u.se - *it);
            q.push(h);
            --it;
        }
    }
}

Compilation message (stderr)

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:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < g[t.u.fi][t.u.se].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43