Beküldés #5 532

2023-07-11 21:14:56

cpp14

Időlimit túllépés 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;
}

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