글 읽기 - 어디가 잘못되었는지 모르겠습니다.. (풀이 관련 스포 있음)

dotorya 8년 전 0

점들을 높이 순서대로 정렬하고 높은 점부터 추가해가며 점을 추가할 때마다 상하좌우의 점과 union&find를 수행,

각 점에 대해 h-D+1 이상의 모든 점을 추가했을 때, 현재 그 점이 연결된 모든 점 중 가장 높은 점인지 확인하는 소스코드입니다.

어제부터 쭉 디버깅해봤는데 어디가 틀렸는지 잘 모르겠네요..

NWERC 대회 공식테케로 확인해봐도 틀린 데이터가 없고요...

혹시 어디가 잘못되었는지 또는 어떤 test case에서 잘못되었는지라도 알 수 있다면 감사하겠습니다!

//*
#include <algorithm>
#include <ctype.h>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <math.h>
#include <queue>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <vector>

#define pow10 pasiodfiopsdjviozjxciovjxcviozj
#define pow2 qpowdskopjkcoizxnzoicn

#pragma warning(disable:4996)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <char, char> pcc;
typedef pair <int, char> pic;
typedef pair <char, int> pci;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef pair <db, int> pdi;

int IT_MAX;
const int MOD = 10007;
const int INF = 1034567891;
const ll LL_INF = 1234567890123456789ll;
const db PI = 3.141592653589793238;

class data{
public:
	int x, y;
	data() {
		*this = data(0, 0);
	}
	data(int a, int b) {
		x = a, y = b;
	}
	bool operator < (const data & l) const {
		if (x - y != l.x - l.y) return x - y < l.x - l.y;
		else return x < l.x;
	}	
};

map <int, int> M;
int in[505][505];
int r[300000];
int mx[300000];
vector <int> V[300000];
vector <data> O;	

int P[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

int root(int x) {
	if (r[x] == -1) return -1;
	return (r[x] == x) ? x : (r[x] = root(r[x]));
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int H, W, D, i, j, ans = 0;
		scanf("%d %d %d", &H, &W, &D);
		for (i = 0; i < H; i++) {
			for (j = 0; j < W; j++) {
				scanf("%d", &in[i][j]);
				r[i*W+j] = -1;
				mx[i*W+j] = -1;
				if (M.count(in[i][j]) == 0) {
					int k = M.size();
					M[in[i][j]] = k;
					O.push_back(data(in[i][j], 0));
					O.push_back(data(in[i][j], D));
				}
				V[M[in[i][j]]].push_back(i*W + j);
			}
		}

		sort(O.begin(), O.end());
		while (!O.empty()) {
			data u = O.back();
			O.pop_back();
			int t = M[u.x];
			if (u.y == 0) {
				for (i = 0; i < V[t].size(); i++) {
					int t2 = V[t][i];
					r[t2] = t2;
					mx[t2] = u.x;
					int tx = t2 / W, ty = t2%W;
					for (j = 0; j < 4; j++) {
						int tx2 = tx + P[j][0], ty2 = ty + P[j][1];
						if (tx2 < 0 || tx2 >= H || ty2 < 0 || ty2 >= W) continue;
						int t3 = tx2*W + ty2;
						int t4 = root(t2);
						int t5 = root(t3);
						if (t4 < 0 || t5 < 0) continue;
						r[t4] = t5;
						mx[t5] = max(mx[t4], mx[t5]);
					}
				}
			}
			else {
				for (i = 0; i < V[t].size(); i++) {
					int t2 = V[t][i];
					int t3 = root(t2);
					if (mx[t3] == u.x) ans++;
					
				}
			}
		}
		if(T != 1) printf("%d\n", ans);
		else printf("%d", ans);

		for (i = 0; i < M.size(); i++) V[i].clear();
		M.clear();
	}
	return 0;
}

//*/

baekjoon 8년 전 0

else printf("%d", ans); 를 else printf("%d\n", ans); 으로 바꾸세요.

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

문제

문제

출처

ICPC

어디가 잘못되었는지 모르겠습니다.. (풀이 관련 스포 있음)

dotorya 8년 전 0

baekjoon 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말