글 읽기 - priority queue때문에 tle가 난걸까요?

ploffer11 5년 전 0

복잡도 먹을만한곳이 priority queue말곤 없어 보이는데 어디가 잘못된걸까요..?

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> t;

int n, m, k;
int food[15][15], board[15][15];
int dr[] = { 1, 1, 1, 0, 0, -1, -1, -1 };
int dc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

priority_queue<t, vector<t>, greater<t>> tree;

queue<t> save;
queue<t> death;

void init()
{
	cin >> n >> m >> k;
	for ( int i = 1; i <= n; i++ )
	{
		for ( int j = 1; j <= n; j++ )
		{
			cin >> food[i][j];
			board[i][j] = 5;
		}
	}

	for ( int i = 0; i < m; i++ )
	{
		int a, b, c;
		cin >> a >> b >> c;
		tree.push({ c, a, b, });
	}
}

void spring()
{
	while ( !tree.empty() )
	{
		auto[age, r, c] = tree.top();
		tree.pop();

		if ( board[r][c] >= age )
		{
			board[r][c] -= age;
			save.push({ age + 1, r, c });
		}

		else death.push({ age, r, c });
	}
}

void summer()
{
	while ( !death.empty() )
	{
		auto[age, r, c] = death.front();
		death.pop();

		board[r][c] += age / 2;
	}
}

void autumn()
{
	while ( !save.empty() )
	{
		auto[age, r, c] = save.front();
		save.pop();

		tree.push({ age, r, c });

		if ( age % 5 == 0 )
		{
			for ( int i = 0; i < 8; i++ )
			{
				int R = r + dr[i], C = c + dc[i];

				if ( 1 <= R && R <= n && 1 <= C && C <= n )
					tree.push({ 1, R, C });
			}
		}
	}
}

void winter()
{
	for ( int i = 1; i <= n; i++ )
	{
		for ( int j = 1; j <= n; j++ )
		{
			board[i][j] += food[i][j];
		}
	}
}

int solve()
{
	for ( int i = 0; i < k; i++ )
	{
		spring();
		summer();
		autumn();
		winter();
	}

	return tree.size();
}

int main()
{
	init();
	cout << solve();
}

ploffer11 5년 전 2

모든 나무 정보를 하나의 pq에 저장하는게 아니라

배열의 각 칸에 나무 정보를 저장함으로써 복잡도를 줄이니 ac를 받았습니다.

역시 pq에 너무 많은 나무들이 들어가는게 문제였나봐요.

djghdy 3년 전 0

혹시 큐를 안쓰신건가요? 우선순위큐로 풀고 싶은데.. 시간초과가나네요..

ploffer11 3년 전 0

데이터 추가로 시간초과가 나길래 그냥 벡터+정렬로 풀었습니다.

여담으로 카운팅소트 풀이도 있습니다.

djghdy 3년 전 0

우선순위 큐보다 벡터+정렬이 더 빠른건가요.. 우선순위큐 pus보다 정렬이 더 빠른가..
답변 감사드립니다

kkk950928 1년 전 0

아하

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

문제

문제

출처

ICPC

priority queue때문에 tle가 난걸까요?

ploffer11 5년 전 0

ploffer11 5년 전 2

djghdy 3년 전 0

ploffer11 3년 전 0

djghdy 3년 전 0

kkk950928 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말