oj.uz

Submission #207547

# Submission time Handle Problem Language Result Execution time Memory
207547 2020-03-07T23:28:53 Z MetB OBELISK (NOI14_obelisk) C++14
25 / 25
 328 ms 95676 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#define N 2000001

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int dx[3] = {-1, 1, 0};

struct Pt {
	ll x, y;
} S, E;

int n, m;

vector <Pt> p[N];
vector <ll> d[N];

ll dist (Pt a, Pt b) {
	ll x = abs (a.x - b.x), y = abs (a.y - b.y);
    if(m == 1)
        return abs(x) + abs(y);
    int ans = (1<<30);
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            for(int g = 0; g < 2; g++)
            {
                for(int h = 0; h < 2; h++)
                {
                    int p = abs(x + dx[i] * (m + 1));
                    int q = abs(y + dx[j] * (m + 1));
                    int t1 = p / (m + 1) + (i < 2);
                    int t2 = q / (m + 1) + (j < 2);
                    int cur = t1 * 2 + t2 * 2 + g * 2 + h * 2;
                    p %= (m + 1);
                    q %= (m + 1);
                    if(p)
                    {
                        if(!t2)
                            cur += 2;
                        if(g)
                            cur += m + 1 - p;
                        else
                            cur += p;
                    }
                    if(q)
                    {
                        if(!t1)
                            cur += 2;
                        if(h)
                            cur += m + 1 - q;
                        else
                            cur += q;
                    }
                    ans = min(ans, cur);
                }
            }
        }
    }
    return ans;
} 

int main () {
	cin >> n >> m;

	cin >> S.x >> S.y >> E.x >> E.y;

	d[0].push_back (0);
	p[0].push_back (S);

	for (int i = 1; i < n; i++) {
		int h;
		cin >> h;
		d[i].resize (h);
		p[i].resize (h);

		for (int j = 0; j < h; j++) {
			cin >> p[i][j].x >> p[i][j].y;
			d[i][j] = INF;

			for (int k = 0; k < p[i-1].size (); k++) {
				d[i][j] = min (d[i][j], d[i-1][k] + dist (p[i-1][k], p[i][j]));
			}
		}
	}

	ll ans = INF;

	for (int i = 0; i < p[n-1].size (); i++) {
		ans = min (ans, d[n-1][i] + dist (p[n-1][i], E));
	}

	cout << (ans == INF ? -1 : ans);
}

Compilation message

obelisk.cpp: In function 'int main()':
obelisk.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < p[i-1].size (); k++) {
                    ~~^~~~~~~~~~~~~~~~
obelisk.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p[n-1].size (); i++) {
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94204 KB Output is correct
2 Correct 57 ms 94328 KB Output is correct
3 Correct 58 ms 94200 KB Output is correct
4 Correct 56 ms 94200 KB Output is correct
5 Correct 57 ms 94204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94260 KB Output is correct
2 Correct 61 ms 94304 KB Output is correct
3 Correct 61 ms 94312 KB Output is correct
4 Correct 64 ms 94316 KB Output is correct
5 Correct 59 ms 94288 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 94932 KB Output is correct
2 Correct 276 ms 95076 KB Output is correct
3 Correct 270 ms 94968 KB Output is correct
4 Correct 281 ms 94968 KB Output is correct
5 Correct 284 ms 95096 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 94980 KB Output is correct
2 Correct 304 ms 95276 KB Output is correct
3 Correct 305 ms 95676 KB Output is correct
4 Correct 328 ms 95328 KB Output is correct
5 Correct 308 ms 95352 KB Output is correct