나무 제테크

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

시간초과

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

struct Tree {
	int x, y, z;
	bool operator <(const Tree& b) const {
		return z < b.z;
	}
};

int n, m, k;
int map[11][11];

int board[11][11];
int dy[] = { -1,-1,-1,0,0,1,1,1 };
int dx[] = { -1,0,1,-1,1,-1,0,1 };

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	vector<Tree> v;
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			cin >> map[y][x];
			board[y][x] = 5;
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		Tree temp;
		temp.x = y;
		temp.y = x;
		temp.z = z;
		v.push_back(temp);
	}
	for (int cnt = 0; cnt < k; cnt++) {
		sort(v.begin(), v.end());
		for (int i = 0; i < v.size(); i++) {//봄,여름
			int y = v[i].y;
			int x = v[i].x;
			int z = v[i].z;
			if (z == -1) continue;
			if (board[y][x] < z) {
				v[i].z = -1;
			}
			else {
				board[y][x] -= v[i].z;
				v[i].z++;
			}
			if (v[i].z == -1) {
				board[y][x] += v[i].z / 2;
				//v[i].z = -2;
				v.erase(v.begin()+i,v.begin()+i+1);
			}
		}
		for (int i = 0; i < v.size(); i++) { //가을
			int y = v[i].y;
			int x = v[i].x;
			int z = v[i].z;
			if (v[i].z == -2) continue;
			if (v[i].z % 5) continue;
			else {
				for (int i = 0; i < 8; i++) {
					int ny = y + dy[i]; int nx = x + dx[i];
					if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
						Tree temp;
						temp.y = ny; temp.x = nx; temp.z = 1;
						v.push_back(temp);
					}
				}
			}
		}
		for (int y = 1; y <= n; y++) { //겨울
			for (int x = 1; x <= n; x++) {
				board[y][x] += map[y][x];
			}
		}
	}
	int answer = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i].z > 0) answer++;
	}
	cout << answer << "\n";
	return 0;
}

 

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

struct TREE {
	int x, y, age;
};

bool cmp(TREE& a, TREE& b) {
	return a.age < b.age;
}

struct QUEUE {
	int f, b;
	TREE tree[684000];

	QUEUE() {
		init();
	}

	void init() {
		f = 0, b = 0;
	}

	bool isempty() {
		return (f == b);
	}

	void push(TREE val) {
		tree[b++] = val;
	}

	void pop() {
		++f;
	}

	TREE front() {
		return tree[f];
	}

	int size() {
		return (b - f);
	}
};

int n, m, k;
QUEUE tree[2];
QUEUE new_tree;
QUEUE dead_tree, birth_of_child_tree;

TREE init_tree[100];

int map[11][11],add[10][10];

int dy[] = { -1,-1,-1,0,0,1,1,1 };
int dx[] = { -1,0,1,-1,1,-1,0,1 };

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> add[y][x];
			map[y][x] = 5;
		}
	}

	for (int i = 0; i < m; i++) {
		cin >> init_tree[i].y >> init_tree[i].x >> init_tree[i].age;
		init_tree[i].y--; init_tree[i].x--;
	}
	sort(init_tree, init_tree + m, cmp);


	int cur = 0, next = 0;
	for (int i = 0; i < m; i++) tree[cur].push(init_tree[i]);

	for (int i = 0; i < k; i++) {
		next = (cur + 1) % 2;
		dead_tree.init();
		birth_of_child_tree.init();
		tree[next].init();
		//봄
		while (!new_tree.isempty()) {
			TREE cur_tree = new_tree.front(); new_tree.pop();
			if (map[cur_tree.y][cur_tree.x] >= cur_tree.age) {
				map[cur_tree.y][cur_tree.x] -= cur_tree.age;
				cur_tree.age++;
				tree[next].push(cur_tree);
			}
			else dead_tree.push(cur_tree);
		}

		while (!tree[cur].isempty()) {
			TREE cur_tree = tree[cur].front(); tree[cur].pop();
			if (map[cur_tree.y][cur_tree.x] >= cur_tree.age) {
				map[cur_tree.y][cur_tree.x] -= cur_tree.age;
				cur_tree.age++;
				tree[next].push(cur_tree);

				if ((cur_tree.age % 5) == 0) birth_of_child_tree.push(cur_tree);
			}
			else dead_tree.push(cur_tree);
		}
		//여름
		while (!dead_tree.isempty()) {
			TREE cur_tree = dead_tree.front(); dead_tree.pop();
			map[cur_tree.y][cur_tree.x] += (cur_tree.age / 2);
		}
		//가을
		new_tree.init();
		while (!birth_of_child_tree.isempty()) {
			TREE cur_tree = birth_of_child_tree.front(); birth_of_child_tree.pop();
			for (int dir = 0; dir < 8; dir++) {
				TREE next_tree;
				next_tree.y = cur_tree.y + dy[dir];
				next_tree.x = cur_tree.x + dx[dir];
				next_tree.age = 1;
				if (next_tree.y < 0 || next_tree.y >= n || next_tree.x < 0 || next_tree.x >= n) {
					continue;
				}
				new_tree.push(next_tree);
			}
		}
		//겨울
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				map[y][x] += add[y][x];
			}
		}
		cur = next;
	}
	cout << tree[next].size() + new_tree.size() << "\n";
	return 0;
}