Submission #207542

#	Time	Username	Problem	Language	Result	Execution time	Memory
207542		MetB	오벨리스크 (NOI14_obelisk)	C++14	5 / 25	134 ms	95352 KiB

obelisk

#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;

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

int n, m;

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

ll dist1D (ll x, bool h, bool v) {
	if (m == 1) return x;
	if (!x) return 0;
	if (!h && !v) return INF;
	if (!h) return x;
	ll d = x / (m + 1);
	ll sx = d * (m + 1);
	if (sx == x) return 2 * d - 2;
	if (!d) return INF;
	ll fromFront = max (0LL, 2 * d - 2) + x - sx;
	ll fromBack = 2 * d + (sx + m + 1) - x;
	return min (fromFront, fromBack);
}

ll dist (Pt a, Pt b) {
	ll x = abs (a.x - b.x), y = abs (a.y - b.y);

	ll ans = INF;

	for (int v = 0; v < 2; v++)
		for (int h = 0; h < 2; h++)
			ans = min (ans, 2 * (h + v) + dist1D(x, h, v) + dist1D(y, v, h));
	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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7