oj.uz

Submission #124620

# Submission time Handle Problem Language Result Execution time Memory
124620 2019-07-03T15:14:13 Z johutha OBELISK (NOI14_obelisk) C++14
19 / 25
 100 ms 13148 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 12204 KB Output is correct
2 Correct 94 ms 11896 KB Output is correct
3 Correct 95 ms 12024 KB Output is correct
4 Correct 100 ms 13148 KB Output is correct
5 Correct 94 ms 12280 KB Output is correct