oj.uz

Submission #938128

# Submission time Handle Problem Language Result Execution time Memory
938128 2024-03-04T21:14:44 Z CpDark OBELISK (NOI14_obelisk) C++17
25 / 25
 44 ms 1176 KB 
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 9;

long long dist1D(long long x, bool useHor, bool useVert, int m) {
    if (m == 1) return x;
    if (!x) return 0;
    if (!useHor && !useVert) return inf;
    if (!useHor) return x;
    long long v = x / (m + 1);
    long long sx = v * (m + 1);
    if (sx == x) return 2 * v - 2;
    if (!useVert) return inf;
    long long fromFront = max(0LL, 2 * v - 2) + x - sx;
    long long fromBack = 2 * v + (sx + m + 1) - x;
    return min(fromFront, fromBack);
}

long long getDist(pair<int, int> a, pair<int, int> b, int m) {
    int x = abs(a.first - b.first), y = abs(a.second - b.second);
    long long ans = inf;
    for (int useVert = 0; useVert < 2; ++useVert) {
        for (int useHor = 0; useHor < 2; ++useHor) {
            ans = min(ans, 2 * (useHor + useVert) + dist1D(x, useHor, useVert, m) + dist1D(y, useVert, useHor, m));
        }
    }
    return ans;
}

vector<vector<pair<int, long long>>> graph;
vector<long long> dist;

long long solve(int n, int m, pair<int, int> s, pair<int, int>e, vector<vector<pair<int, int>>> holes) {    
    int counter = 0;
    for (int i = 0;i < holes.size();i++) counter += holes[i].size();
    vector<vector<int>> id(holes.size());
    dist.resize(counter + 2, inf);
    dist[0] = 0;

    int index = 1;
    for (int i = 0;i < holes.size();i++) {
        id[i].resize(holes[i].size());
        for (int j = 0;j < holes[i].size();j++) {
            id[i][j] = index++;
            // if first level calc min dist from start point
            if (i == 0) dist[id[i][j]] = min(dist[id[i][j]], dist[0] + getDist(s, holes[i][j], m));

            // cacl min dist to this level from all holes in the previous level
            if (i > 0) {
                for (int k = 0;k < holes[i - 1].size();k++) {
                    dist[id[i][j]] = min(dist[id[i][j]], dist[id[i - 1][k]] + getDist(holes[i - 1][k], holes[i][j], m));
                }
            }

            // if last level cacl min dist to end point via last level holes
            if (i == holes.size() - 1) dist[counter + 1] = min(dist[counter + 1], dist[id[i][j]] + getDist(holes[i][j], e, m));
        }
    }

    return dist[index];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    pair<int, int> S, E;
    cin >> N >> M >> S.first >> S.second >> E.first >> E.second;

    vector<vector<pair<int, int>>> H(N - 1);
    for (int i = 0;i < N - 1;i++) {
        cin >> K;
        H[i].resize(K);
        for (int j = 0;j < K;j++) cin >> H[i][j].first >> H[i][j].second;
    }

    cout << solve(N, M, S, E, H);
    return 0;
}

Compilation message

obelisk.cpp: In function 'long long int solve(int, int, std::pair<int, int>, std::pair<int, int>, std::vector<std::vector<std::pair<int, int> > >)':
obelisk.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0;i < holes.size();i++) counter += holes[i].size();
      |                    ~~^~~~~~~~~~~~~~
obelisk.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0;i < holes.size();i++) {
      |                    ~~^~~~~~~~~~~~~~
obelisk.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int j = 0;j < holes[i].size();j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
obelisk.cpp:50:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 for (int k = 0;k < holes[i - 1].size();k++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~~~
obelisk.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if (i == holes.size() - 1) dist[counter + 1] = min(dist[counter + 1], dist[id[i][j]] + getDist(holes[i][j], e, m));
      |                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 500 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1152 KB Output is correct
2 Correct 35 ms 1116 KB Output is correct
3 Correct 35 ms 1116 KB Output is correct
4 Correct 35 ms 1176 KB Output is correct
5 Correct 44 ms 1136 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1164 KB Output is correct
2 Correct 36 ms 1124 KB Output is correct
3 Correct 35 ms 1116 KB Output is correct
4 Correct 39 ms 1116 KB Output is correct
5 Correct 36 ms 1124 KB Output is correct