oj.uz

Submission #124589

# Submission time Handle Problem Language Result Execution time Memory
124589 2019-07-03T14:40:52 Z johutha OBELISK (NOI14_obelisk) C++14
5 / 25
 89 ms 12280 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 hormoves = abs(ix - ox) / (k + 1);
        int vermoves = abs(iy - oy) / (k + 1);
        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.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 296 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 7.0

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