글 읽기 - 시간과 관련해서 질문이 있습니다

kdr06006 4년 전 0

안녕하세요 병렬이분탐색을 공부하고 있습니다.

제 나름대로 병렬이분탐색을 짜보았는데 계속 시간초과가 나서 질문을 드립니다.

제가 계산한 시간은 큰 while문은 log(_max)번,

그 안에서 도는 시간은 대략 _max + q + N*M번으로 두개를 곱하면 7초안에는 들어올 줄 알았는데 시간초과가 뜨는군요.

조언 부탁드립니다!

(수정) 시간초과 뜨는 이유를 알았는데 make()부분을 어떻게 하면 빠르게 처리할 수 있을지 모르겠습니다..

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int _size = 1e5 + 1, _max = 250001;
typedef struct { int x, y; }pii;
int map[501][501], N, M, p[_max];
int dx[] = { 0,1 }, dy[] = { 1,0 };
pii query[_size][2], H[_size];
vector<int>adj[_max], arr;
bool check[_size * 10];

inline int num(int x, int y) { return (x - 1) * M + y; }
inline int get(int x) { return x == p[x] ? x : p[x] = get(p[x]); }
inline void uni(int a, int b) { a < b ? p[b] = a : p[a] = b; }

void make(int h)
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] > h) continue;
			for (int k = 0; k < 2; k++) {
				int X = i + dx[k], Y = j + dy[k];
				if (X <= N && Y <= M && map[X][Y] <= h)
					uni(get(num(i, j)), get(num(X, Y)));
			}
		}
	}
}

int main()
{
	ios::ios_base::sync_with_stdio(NULL);
	cin.tie(0); cout.tie(0);
	int q, l = 1e9, r = -1e9;
	cin >> N >> M >> q;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (!check[map[i][j]]) arr.push_back(map[i][j]);
			check[map[i][j]] = true;
		}
	}

	sort(arr.begin(), arr.end());
	l = 0, r = arr.size() - 1;

	for (int i = 0; i < q; i++) {
		cin >> query[i][0].x >> query[i][0].y >> query[i][1].x >> query[i][1].y;
		H[i] = { l,r };
	}

	while (1) {
		for (int i = 0; i < arr.size(); i++) 
			adj[i].clear();
		bool flag = true;
		for (int i = 0; i < q; i++) {
			if (H[i].x > H[i].y) continue;
			adj[H[i].x + H[i].y >> 1].push_back(i);
			flag = false;
		}
		if (flag) break;

		for (int i = 1; i <= N * M; i++) p[i] = i;

		for (int i = 0; i < arr.size(); i++) {
			make(arr[i]);
			for (auto a : adj[i]) {
				if (get(num(query[a][0].x, query[a][0].y)) == get(num(query[a][1].x, query[a][1].y)))
					H[a].y = i - 1;
				else H[a].x = i + 1;
			}
		}
	}

	for (int i = 0; i < q; i++) cout << arr[H[i].y + 1] << '\n';
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간과 관련해서 질문이 있습니다

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말