글 읽기 - 빠른 입출력 질문입니다

oh20020409 1년 전 0

ios_base::sync_with_stdio(false);

cin.tie(NULL); cout.tie(NULL);

위의 구문을 넣기 전에는 맞았는데요.

시간 좀 줄여보려고 넣었더니 틀렸습니다. printf와 scanf를 같이 사용하는 것이 아닌데 왜 틀렸는지 모르겠습니다.

#include<iostream>
#include<stack>
#include<utility>
#include<algorithm>
#include<set>
using namespace std;
bool Map[1001][1001];
int visited[1001][1001];
pair<int, int> Map_bfsSize[1001][1001];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int N, M;
int bfsSize;
stack<pair<int, int>> st;
void bfs(int y, int x)
{
	visited[y][x] = true;
	st.push({ y,x });
	bfsSize++;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (!visited[ny][nx] && Map[ny][nx])
		{
			bfs(ny, nx);
		}
	}
}
int sum(int y, int x)
{
	int tmp = 0;
	set<int> s;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!(1 <= ny && ny <= N && 1 <= nx && nx <= M)) continue;
		int id = Map_bfsSize[ny][nx].first;
		int cost = Map_bfsSize[ny][nx].second;
		if (s.find(id) == s.end())
		{
			s.insert(id);
			tmp += cost;
		}
	}
	return tmp + 1;
}
int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> Map[i][j];
	int id = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			if (!visited[i][j] && Map[i][j])
			{
				bfsSize = 0;
				bfs(i, j);
				while (!st.empty())
				{
					int y = st.top().first;
					int x = st.top().second;
					Map_bfsSize[y][x] = { id,bfsSize };
					st.pop();
				}
				id++;
			}
		}
	int result = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			if (!Map[i][j])
			{
				result = max(result, sum(i, j));
			}
		}
	cout << result;
}

seawon0808 1년 전 0

빠른 입출력을 사용한 코드도 올려주세요.

yuris 1년 전 0

반례입니다. fastIO를 뺀 코드에서도 오답이 나오네요.

oh20020409 1년 전 0

오... 감사합니다!

55번 줄에서 id를 0부터 시작하니 각 영역의 id를 확인하여 계산할 떄 중복 여부를 판별했는데, id를 0부터 시작해버리면 계산을 하지 않은 부분 즉 영역이 없는 0인 부분들도 id가 0으로 되어있어서(전역변수) 그랬나봅니다.

id를 1로 바꿔서 계산하니 잘됩니다. 반례 감사드려요! ㅎ.ㅎ

oh20020409 1년 전 0

근데 이문제는 막 그렇게 빨라지진 않네용 ㅎ.ㅎ

seawon0808 1년 전 0

최대 1000*1000개 까지만 입력이 들어와서 그런 것 같네요.

oh20020409 1년 전 1

그렇군요 >.<

글 달아주신 것만으로도 감사합니다. 안녕히주무세요!

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

문제

문제

출처

ICPC

빠른 입출력 질문입니다

oh20020409 1년 전 0

seawon0808 1년 전 0

yuris 1년 전 0

oh20020409 1년 전 0

oh20020409 1년 전 0

seawon0808 1년 전 0

oh20020409 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말