Submission #124592

#	Time	Username	Problem	Language	Result	Execution time	Memory
124592		johutha	OBELISK (NOI14_obelisk)	C++14	5 / 25	87 ms	11896 KiB

obelisk

#include <iostream>
#include <vector>
#include <algorithm>

#define int int64_t

using namespace std;

int k;

struct layer
{
    vector<vector<int>> way;
    vector<pair<int,int>> in;
    vector<pair<int,int>> out;

    int is, os;

    int calcdist(int fr, int to)
    {
        if (k == 1) return abs(in[fr].first - out[to].first) + abs(in[fr].second - out[to].second);
        int ix = in[fr].first, iy = in[fr].second, ox = out[to].first, oy = out[to].second;
        int hormoves = abs(ix - ox) / (k + 1);
        int vermoves = abs(iy - oy) / (k + 1);
        hormoves *= 2;
        vermoves *= 2;
        if (hormoves == 0 && (abs(iy - oy) % (k + 1)) != 0) hormoves += 2;
        hormoves += (abs(iy - oy) % (k + 1));
        if (vermoves == 0 && (abs(ix - ox) % (k + 1)) != 0) vermoves += 2;
        vermoves += (abs(ix - ox) % (k + 1));
        return vermoves + hormoves;
    }

    void calcways()
    {
        way.resize(is, vector<int>(os));
        for (int i = 0; i < is; i++)
        {
            for (int j = 0; j < os; j++)
            {
                way[i][j] = calcdist(i, j);
            }
        }
    }
};

signed main()
{
    int fl;
    cin >> fl >> k;

    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;

    vector<layer> layers;

    for (int i = 0; i < fl - 1; i++)
    {
        int s;
        cin >> s;
        vector<pair<int,int>> ip(s);
        for (int h = 0; h < s; h++)
        {
            cin >> ip[h].first >> ip[h].second;
        }
        layer l;
        if (i == 0)
        {
            l.is = 1;
            l.in.push_back({sx, sy});
        }
        else
        {
            l.is = layers.back().os;
            l.in = layers.back().out;
        }
        l.os = s;
        l.out = ip;
        layers.push_back(l);
    }
    layer l;
    l.is = layers.back().os;
    l.in = layers.back().out;
    l.os = 1;
    l.out = {{ex, ey}};
    layers.push_back(l);
    for (auto &la : layers)
    {
        la.calcways();
    }
    vector<int> fast(1, 0);
    for (int i = 0; i < fl; i++)
    {
        layer cl = layers[i];
        vector<int> nfast(cl.os);
        for (int o = 0; o < cl.os; o++)
        {
            int mmin = 1e12;
            for (int in = 0; in < cl.is; in++)
            {
                mmin = min(mmin, cl.way[in][o] + fast[in]);
            }
            nfast[o] = mmin;
        }
        fast = nfast;
    }
    cout << fast[0] << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7