Submission #124620

#	Time	Username	Problem	Language	Result	Execution time	Memory
124620		johutha	OBELISK (NOI14_obelisk)	C++14	19 / 25	100 ms	13148 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 diffx = abs(ix - ox), diffy = abs(iy - oy);
        int l = k + 1;
        int hrm = 0;
        int vrm = 0;
        int hm = diffx / l;
        int vm = diffy / l;
        if (diffx % l > l - (diffx % l)) hm++; 
        if (diffy % l > l - (diffy % l)) vm++;
        hrm = min(l - (diffx % l), diffx % l);
        vrm = min(l - (diffy % l), diffy % l);
        if (vrm && hm == 0) hm++;
        if (hrm && vm == 0) vm++;
        //cout << hm << " " << hrm << " " << vm << " " << vrm << "\n";
        return 2*vm + hrm + 2*hm + vrm;
    }

    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;
    if (fl != 1)
    {
        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);
    }
    else
    {
        layer l;
        l.is = 1;
        l.os = 1;
        l.in = {{sx, sy}};
        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: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 7 / 7