Submission #5,532

2023-07-11 21:14:56

cpp14

Time limit exceeded 65/100

597ms

44824 KiB

#include <bits/stdc++.h>
using namespace std;

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

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

int prim(vector<vector<pair<int, int>>>& graph, int startVertex) {
    int N = graph.size();
    // Priority queue to store the edges and their weights
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // Create a vector to track visited vertices
    vector<bool> visited(N, false);
    // Add the starting vertex to the priority queue
    pq.push(make_pair(0, startVertex));
    vector<pair<int, int>> mst;  // Minimum spanning tree
    while (!pq.empty()) {
        // Extract the minimum weight edge from the priority queue
        pair<int, int> curr = pq.top();
        pq.pop();
        int weight = curr.first;
        int vertex = curr.second;
        if (visited[vertex]) {
            continue;
        }
        // Mark the current vertex as visited
        visited[vertex] = true;
        // Add the current edge to the minimum spanning tree
        mst.push_back(make_pair(weight, vertex));
        // Iterate through all adjacent vertices of the current vertex
        for (pair<int, int>& edge : graph[vertex]) {
            int adjVertex = edge.first;
            int adjWeight = edge.second;
            if (!visited[adjVertex]) {
                // Add the adjacent vertex and its weight to the priority queue
                pq.push(make_pair(adjWeight, adjVertex));
            }
        }
    }
    // Find the maximum weight among the edges in the MST
    int maxWeight = 0;
    for (pair<int, int>& edge : mst) {
        maxWeight = max(maxWeight, edge.first);
    }
    return maxWeight;
}

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);
	int N = ru();
	v.resize(N);
	for (int i = 0; i < N; i++) {
		v[i].x = ru();
		v[i].y = ru();
	}
	vector<int> w(N);
	iota(w.begin(), w.end(), 0);
	vector<vector<pair<int, int>>> g(N);
	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) {
			g[w[i]].push_back({r, d1(v[r]) - d1(v[w[i]])});
			g[r].push_back({w[i], d1(v[r]) - d1(v[w[i]])});
		}
	}
	// 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) {
			g[w[i]].push_back({r, d4(v[r]) - d4(v[w[i]])});
			g[r].push_back({w[i], d4(v[r]) - d4(v[w[i]])});
		}
	}
	// 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;
		f[i].assign(w.begin() + s, w.begin() + e);
		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) {
			g[w[i]].push_back({r, d2(v[r]) - d2(v[w[i]])});
			g[r].push_back({w[i], d2(v[r]) - d2(v[w[i]])});
		}
	}
	// 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;
		f[i].assign(w.begin() + s, w.begin() + e);
		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) {
			g[w[i]].push_back({r, d3(v[r]) - d3(v[w[i]])});
			g[r].push_back({w[i], d3(v[r]) - d3(v[w[i]])});
		}
	}
	cout << prim(g, 0) << endl;
	return 0;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	3ms	1824 KiB
		2	Time limit exceeded	597ms	30872 KiB
subtask2	15/15
		3	Accepted	7ms	4632 KiB
		4	Accepted	7ms	4856 KiB
		5	Accepted	7ms	5084 KiB
		6	Accepted	7ms	5196 KiB
		7	Accepted	3ms	5000 KiB
subtask3	15/15
		8	Accepted	7ms	4632 KiB
		9	Accepted	7ms	4856 KiB
		10	Accepted	7ms	5084 KiB
		11	Accepted	7ms	5196 KiB
		12	Accepted	3ms	5000 KiB
		13	Accepted	4ms	5388 KiB
		14	Accepted	7ms	5868 KiB
		15	Accepted	7ms	6108 KiB
		16	Accepted	7ms	6284 KiB
		17	Accepted	7ms	6512 KiB
subtask4	35/35
		18	Accepted	7ms	4632 KiB
		19	Accepted	7ms	4856 KiB
		20	Accepted	7ms	5084 KiB
		21	Accepted	7ms	5196 KiB
		22	Accepted	3ms	5000 KiB
		23	Accepted	4ms	5388 KiB
		24	Accepted	7ms	5868 KiB
		25	Accepted	7ms	6108 KiB
		26	Accepted	7ms	6284 KiB
		27	Accepted	7ms	6512 KiB
		28	Accepted	7ms	6664 KiB
		29	Accepted	164ms	20500 KiB
		30	Accepted	259ms	28052 KiB
		31	Accepted	266ms	28440 KiB
		32	Accepted	146ms	30908 KiB
subtask5	0/35
		33	Accepted	7ms	4632 KiB
		34	Accepted	7ms	4856 KiB
		35	Accepted	7ms	5084 KiB
		36	Accepted	7ms	5196 KiB
		37	Accepted	3ms	5000 KiB
		38	Accepted	4ms	5388 KiB
		39	Accepted	7ms	5868 KiB
		40	Accepted	7ms	6108 KiB
		41	Accepted	7ms	6284 KiB
		42	Accepted	7ms	6512 KiB
		43	Accepted	7ms	6664 KiB
		44	Accepted	164ms	20500 KiB
		45	Accepted	259ms	28052 KiB
		46	Accepted	266ms	28440 KiB
		47	Accepted	146ms	30908 KiB
		48	Time limit exceeded	513ms	44824 KiB
		49	Time limit exceeded	555ms	33440 KiB
		50	Time limit exceeded	573ms	33500 KiB
		51	Time limit exceeded	559ms	33496 KiB
		52	Time limit exceeded	583ms	33456 KiB