55332023-07-11 21:46:31111Drónfutárcpp14Időlimit túllépés 65/100597ms34796 KiB
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

#define rand() (rand() | rand() << 16)

#define LSB(x) ((x) & -(x))

struct Pt { int x, y; };

int c1(Pt p) { return - p.x + p.y; }
int c2(Pt p) { return + p.x - p.y; }
int c3(Pt p) { return - p.x - p.y; }
int c4(Pt p) { return + p.x + p.y; }

int d1(Pt p) { return + p.x + p.y; }
int d2(Pt p) { return + p.x + p.y; }
int d3(Pt p) { return - p.x + p.y; }
int d4(Pt p) { return - p.x + p.y; }

char* pi = new char[10000000];

unsigned int ru() {
    while (!isdigit(*pi)) {
        pi++;
    }
    int r = 0;
    while (isdigit(*pi)) {
        r *= 10;
        r += *pi - '0';
        pi++;
    }
    return r;
}

vector<Pt> v;

int cmpy(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	if (a.y > b.y) {
		return -1;
    }
    else if (a.y < b.y) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmpxl(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	if (a.x < b.x) {
		return -1;
    }
    else if (a.x > b.x) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmpxh(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	if (a.x > b.x) {
		return -1;
    }
    else if (a.x < b.x) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp1(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c1(a);
	int cb = c1(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp2(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c2(a);
	int cb = c2(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp3(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c3(a);
	int cb = c3(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp4(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c4(a);
	int cb = c4(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int main() {
    fread(pi, 10000000, 1, stdin);
//    fread(pi, 10000000, 1, fopen("be2.txt", "r"));
	int N = ru();
	v.resize(N);
	vector<vector<pii>> g(N);
	for (int i = 0; i < N; i++) {
		v[i].x = ru();
		v[i].y = ru();
		g[i].reserve(8);
	}
	vector<int> w(N);
	iota(w.begin(), w.end(), 0);
	vector<vector<int>> f(N + 1);
	vector<vector<int>> t(N + 1);
	// octant 1
	qsort(w.data(), w.size(), sizeof(int), cmpy);
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		f[i].assign(w.begin() + s, w.begin() + e);
		t[i].resize(e - s);
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp1);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d1(v[f[i][j]]) < d1(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h = N - 1;
		while (l != h) {
			int m = (l + h + 1) / 2;
			if (v[w[m]].y == v[w[i]].y) {
				l = m;
			}
			else {
				h = m - 1;
			}
		}
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c1(v[f[j][m]]) < c1(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d1(v[t[j][l]]) < d1(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d1(v[r]) - d1(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	// octant 4
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp4);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d4(v[f[i][j]]) < d4(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h;
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c4(v[f[j][m]]) <= c4(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d4(v[t[j][l]]) < d4(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d4(v[r]) - d4(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	// octant 2
	qsort(w.data(), w.size(), sizeof(int), cmpxh);
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		copy(w.begin() + s, w.begin() + e, f[i].begin());
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp2);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d2(v[f[i][j]]) < d2(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h;
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c2(v[f[j][m]]) <= c2(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d2(v[t[j][l]]) < d2(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d2(v[r]) - d2(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	// octant 3
	qsort(w.data(), w.size(), sizeof(int), cmpxl);
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		copy(w.begin() + s, w.begin() + e, f[i].begin());
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp3);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d3(v[f[i][j]]) < d3(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h = N - 1;
		while (l != h) {
			int m = (l + h + 1) / 2;
			if (v[w[m]].x == v[w[i]].x) {
				l = m;
			}
			else {
				h = m - 1;
			}
		}
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c3(v[f[j][m]]) < c3(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d3(v[t[j][l]]) < d3(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d3(v[r]) - d3(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	int ans = 0;
	vector<bool> vis(N);
	set<pii> s;
	s.insert({0, 0});
	while (!s.empty()) {
        auto a = *s.begin();
        s.erase(s.begin());
        if (vis[a.second]) {
            continue;
        }
        vis[a.second] = true;
		ans = max(ans, a.first);
        for (auto p : g[a.second]) {
            if (!vis[p.first]) {
                s.insert({p.second, p.first});
            }
        }
    }
    cout << ans << endl;
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1888 KiB
2Időlimit túllépés597ms32872 KiB
subtask215/15
3Elfogadva7ms4788 KiB
4Elfogadva7ms5020 KiB
5Elfogadva7ms5232 KiB
6Elfogadva7ms5476 KiB
7Elfogadva3ms5172 KiB
subtask315/15
8Elfogadva7ms4788 KiB
9Elfogadva7ms5020 KiB
10Elfogadva7ms5232 KiB
11Elfogadva7ms5476 KiB
12Elfogadva3ms5172 KiB
13Elfogadva4ms5660 KiB
14Elfogadva7ms6176 KiB
15Elfogadva7ms6256 KiB
16Elfogadva7ms6456 KiB
17Elfogadva7ms6564 KiB
subtask435/35
18Elfogadva7ms4788 KiB
19Elfogadva7ms5020 KiB
20Elfogadva7ms5232 KiB
21Elfogadva7ms5476 KiB
22Elfogadva3ms5172 KiB
23Elfogadva4ms5660 KiB
24Elfogadva7ms6176 KiB
25Elfogadva7ms6256 KiB
26Elfogadva7ms6456 KiB
27Elfogadva7ms6564 KiB
28Elfogadva7ms6708 KiB
29Elfogadva171ms22520 KiB
30Elfogadva270ms31364 KiB
31Elfogadva275ms31972 KiB
32Elfogadva142ms34796 KiB
subtask50/35
33Elfogadva7ms4788 KiB
34Elfogadva7ms5020 KiB
35Elfogadva7ms5232 KiB
36Elfogadva7ms5476 KiB
37Elfogadva3ms5172 KiB
38Elfogadva4ms5660 KiB
39Elfogadva7ms6176 KiB
40Elfogadva7ms6256 KiB
41Elfogadva7ms6456 KiB
42Elfogadva7ms6564 KiB
43Elfogadva7ms6708 KiB
44Elfogadva171ms22520 KiB
45Elfogadva270ms31364 KiB
46Elfogadva275ms31972 KiB
47Elfogadva142ms34796 KiB
48Időlimit túllépés547ms28884 KiB
49Időlimit túllépés573ms33480 KiB
50Időlimit túllépés568ms33392 KiB
51Időlimit túllépés551ms33484 KiB
52Időlimit túllépés568ms33488 KiB