백준 나무재태크 문제인데


1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int N, M, K;
int drc[] = { -1,-1,-1,0,1,1,1,0,-1,0,1,1,1,0,-1,-1 };
int energy[11][11], add[11][11], death[11][11];
priority_queue<int, vector<int>, greater<int>> tree[11][11];
bool chk(int r, int c) {
if (!(r<1 || c<1 || r>N || c>N)) return true;
else return false;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> M >> K;
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
cin >> add[r][c];
energy[r][c] = 5;
}
}
for (int i = 0; i < M; i++) {
int r, c, a;
cin >> r >> c >> a;
tree[r][c].push(a);
}
while (K--) {
//봄
int nowE = 0;
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (tree[r][c].size() == 0)continue;
priority_queue<int, vector<int>, greater<int>> tmp;
while (!tree[r][c].empty()) {
int top = tree[r][c].top();
tree[r][c].pop();
if (top <= energy[r][c]) {
energy[r][c] -= top;
tmp.push(top + 1);
}
else {
death[r][c] += (top / 2);
}
}
tree[r][c] = tmp;
}
}
//여름
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (death[r][c] == 0)continue;
energy[r][c] += death[r][c];
death[r][c] = 0;
}
}
//가을
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (tree[r][c].size() == 0)continue;
priority_queue<int, vector<int>, greater<int>> tmp;
tmp = tree[r][c];
while (!tmp.empty()) {
int top = tmp.top();
tmp.pop();
if (top % 5 != 0)continue;
for (int d = 0; d < 8; d++) {
int nr = r + drc[d];
int nc = c + drc[d + 8];
if (!chk(nr, nc))continue;
tree[nr][nc].push(1);
}
}
}
}
//겨울
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
energy[r][c] += add[r][c];
}
}
}
int ans = 0;
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (tree[r][c].size() == 0)continue;
ans += tree[r][c].size();
}
}
cout << ans;
return 0;
}
cs

2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <algorithm>
#define vi vector<int>  
#define vii vector<vi>
#define viii vector<vii>
using namespace std;
int N, M, K;
int drc[] = { -1,-1,-1,0,1,1,1,0,-1,0,1,1,1,0,-1,-1 };
int energy[11][11], add[11][11], death[11][11];
vector<int> tree[11][11];
//viii tree(11, vii(11));
 
bool chk(int r, int c) {
    if (!(r<1 || c<1 || r>N || c>N)) return true;
    else return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M >> K;
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            cin >> add[r][c];
            energy[r][c] = 5;
        }
    }
    for (int i = 0; i < M; i++) {
        int r, c, a;
        cin >> r >> c >> a;
        tree[r][c].push_back(a);
    }
    while (K--) {
        //봄
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (tree[r][c].size() == 0)continue;
                vector<int>tmp;
                sort(tree[r][c].begin(), tree[r][c].end());
                for(int i=0;i<tree[r][c].size();i++) {
                    if (tree[r][c][i] <= energy[r][c]) {
                        energy[r][c] -= tree[r][c][i];
                        tmp.push_back(tree[r][c][i] + 1);
                    }
                    else {
                        death[r][c] += (tree[r][c][i] / 2);
                    }
                }
                tree[r][c].clear();
                for (int i = 0; i < tmp.size(); i++)
                    tree[r][c].push_back(tmp[i]);
            }
        }
 
        //여름
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (death[r][c] == 0)continue;
                energy[r][c] += death[r][c];
                death[r][c] = 0;
            }
        }
 
        //가을
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (tree[r][c].size() == 0)continue;
                for(int i=0;i<tree[r][c].size();i++) {
                    int top = tree[r][c][i];
                    if (top % 5 != 0)continue;
                    for (int d = 0; d < 8; d++) {
                        int nr = r + drc[d];
                        int nc = c + drc[d + 8];
                        if (!chk(nr, nc))continue;
                        tree[nr][nc].push_back(1);
                    }
                }
            }
        }
        //겨울
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                energy[r][c] += add[r][c];
            }
        }
    }
    int ans = 0;
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            if (tree[r][c].size() == 0)continue;
            ans += tree[r][c].size();
        }
    }
    cout << ans;
    return 0;
}
 
cs


위 코드는 우선순위 큐 써서 풀었고

아래코드는 벡터 써서 풀었는데


우선순위 큐 사용한건 시간초과나고

벡터 사용한건 AC함


시간초과 나는 이유가 생각엔 우선순위큐를 복사하는 tmp = tree[r][c]; 이런 과정에서 시간이 많이 걸리나 싶은데

끽 해봐야 O(n)인거 같은데 매번 넣고 정렬하는거 보단 빠를거 같은데...


우선순위 큐 쓴건 왜 시간초과인지 가르침을 주실분 있나요?