Submission #448051

#	Time	Username	Problem	Language	Result	Execution time	Memory
448051		blue	Sky Walking (IOI19_walk)	C++17	10 / 100	43 ms	8832 KiB

walk

#include "walk.h"
#include <vector>
#include <set>
using namespace std;

const long long INF = 1'000'000'000'000'000'000LL;

vector<int> edge[10000];
vector<long long> wt[10000];
vector<long long> src_dist(10000, INF);

void add_edge(int u, int v, long long w)
{
    edge[u].push_back(v);
    wt[u].push_back(w);

    edge[v].push_back(u);
    wt[v].push_back(w);
}

long long abs_diff(long long p, long long q)
{
    return max(p-q, q-p);
}

struct pos
{
    int i;
};

bool operator < (pos X, pos Y)
{
    if(src_dist[X.i] == src_dist[Y.i]) return X.i < Y.i;
    return src_dist[X.i] < src_dist[Y.i];
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{
    int N = x.size();
    int M1 = y.size();

    for(int i = 0; i < N; i++)
    {
        l.push_back(i);
        r.push_back(i);
        y.push_back(0);
    }

    int M = y.size();

    for(int i = 0; i < N; i++)
    {
        for(int j1 = 0; j1 < M; j1++)
        {
            if(i < l[j1] || r[j1] < i || h[i] < y[j1]) continue;
            for(int j2 = j1+1; j2 < M; j2++)
            {
                if(i < l[j2] || r[j2] < i || h[i] < y[j2]) continue;
                add_edge(M*i + j1, M*i + j2, abs_diff(y[j1], y[j2]));
            }
        }
    }

    for(int i1 = 0; i1 < N; i1++)
    {
        for(int i2 = i1+1; i2 < N; i2++)
        {
            for(int j = 0; j < M; j++)
            {
                if(i1 < l[j] || r[j] < i1 || h[i1] < y[j]) continue;
                if(i2 < l[j] || r[j] < i2 || h[i2] < y[j]) continue;
                add_edge(M*i1 + j, M*i2 + j, x[i2] - x[i1]);
            }
        }
    }

    set<pos> tbv;

    int src = M*s + (M1+s);
    int dst = M*g + (M1+g);

    src_dist[src] = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            tbv.insert(pos{M*i + j});

    while(!tbv.empty())
    {
        int u = tbv.begin()->i;
        tbv.erase(tbv.begin());

        for(int e = 0; e < edge[u].size(); e++)
        {
            int v = edge[u][e];
            long long w = wt[u][e];

            if(src_dist[v] > src_dist[u] + w)
            {
                tbv.erase(pos{v});
                src_dist[v] = src_dist[u] + w;
                tbv.insert(pos{v});
            }
        }
    }

    if(src_dist[M*g + (M1 + g)] >= INF) return -1;
    else return src_dist[M*g + (M1 + g)];
}

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:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int e = 0; e < edge[u].size(); e++)
      |                        ~~^~~~~~~~~~~~~~~~
walk.cpp:80:9: warning: unused variable 'dst' [-Wunused-variable]
   80 |     int dst = M*g + (M1+g);
      |         ^~~

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