QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #332121 | #3606. Painted Corridors | ishmeal# | AC ✓ | 797ms | 82784kb | C++14 | 1.8kb | 2024-02-19 09:23:52 | 2024-02-19 09:23:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 10005;
vector<vector<vector<bool>>> vis(MAXN, vector<vector<bool>>(MAXN, vector<bool>(MAXN, false)));
vector<bool> vis_edge(MAXM, 0);
vector<tuple<int, char, int>> graph[MAXN];
void dfs(int r, int b, int y) {
if (vis[r][b][y]) return;
vis[r][b][y] = true;
for (auto [to, color, id] : graph[r]) {
if (color == 'R' || color == 'X') {
vis_edge[id] = true;
dfs(to, b, y);
}
if (color == 'P' && r == b) {
vis_edge[id] = true;
dfs(to, to, y);
}
if (color == 'O' && r == y) {
vis_edge[id] = true;
dfs(to, b, to);
}
}
for (auto [to, color, id] : graph[b]) {
if (color == 'B' || color == 'X') {
vis_edge[id] = true;
dfs(r, to, y);
}
if (color == 'P' && b == r) {
vis_edge[id] = true;
dfs(to, to, y);
}
if (color == 'G' && b == y) {
vis_edge[id] = true;
dfs(r, to, to);
}
}
for (auto [to, color, id] : graph[y]) {
if (color == 'Y' || color == 'X') {
vis_edge[id] = true;
dfs(r, b, to);
}
if (color == 'G' && y == b) {
vis_edge[id] = true;
dfs(r, to, to);
}
if (color == 'O' && y == r) {
vis_edge[id] = true;
dfs(to, b, to);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, r, b, y;
cin >> n >> m >> r >> b >> y;
r--; b--; y--;
for (int i = 0; i < m; i++) {
int u, v;
char c;
cin >> u >> v >> c;
u--; v--;
graph[u].push_back({v, c, i});
graph[v].push_back({u, c, i});
}
dfs(r, b, y);
bool possible = true;
for (int i = 0; i < n; i++) {
for (auto [to, color, id] : graph[i]) {
if (color != 'X' && !vis_edge[id]) {
possible = false;
break;
}
}
if (!possible) break;
}
cout << (possible ? 1 : 0) << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4400kb
input:
6 5 1 2 5 1 3 X 2 3 X 3 4 P 4 5 X 4 6 Y
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 4316kb
input:
6 5 1 2 5 1 3 X 2 3 X 3 4 O 4 5 X 4 6 Y
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4596kb
input:
6 5 1 2 5 1 3 X 2 3 X 3 4 P 4 5 X 4 6 G
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4608kb
input:
3 3 1 1 1 1 2 P 2 3 O 1 3 G
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4336kb
input:
6 6 1 6 1 1 2 R 2 3 P 3 4 R 4 5 P 2 6 B 4 6 B
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 4404kb
input:
7 9 1 2 3 1 4 R 1 5 R 2 4 B 2 6 B 3 5 Y 3 6 Y 4 7 P 5 7 O 6 7 G
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4396kb
input:
12 13 1 2 3 1 4 R 2 4 B 2 5 B 3 5 Y 4 6 P 5 7 G 6 8 R 6 9 B 7 9 B 7 10 Y 8 11 R 10 11 Y 11 12 O
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4316kb
input:
5 7 1 1 1 1 2 B 1 3 P 1 4 R 2 3 P 3 4 P 2 5 R 4 5 B
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4400kb
input:
9 8 1 1 1 1 2 X 1 3 X 2 4 R 2 5 O 2 6 Y 3 7 P 3 8 B 3 9 G
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 2ms
memory: 4332kb
input:
8 7 4 5 1 1 4 R 2 4 B 3 4 P 5 6 R 5 7 B 5 8 P 4 5 X
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 2ms
memory: 4600kb
input:
100 1 10 20 30 77 88 X
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 2ms
memory: 4316kb
input:
100 2 10 20 30 10 11 R 12 13 R
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 162ms
memory: 76456kb
input:
100 765 11 68 21 1 5 Y 1 7 Y 1 12 R 1 13 B 1 20 Y 1 35 Y 1 36 B 1 49 R 1 51 R 1 56 R 1 82 Y 1 91 Y 1 95 B 2 3 B 2 19 R 2 23 B 2 24 R 2 32 B 2 36 R 2 44 R 2 68 R 2 73 B 2 75 B 2 76 R 2 77 B 2 80 B 2 82 Y 2 95 B 3 10 R 3 11 B 3 21 B 3 30 B 3 40 B 3 44 R 3 48 R 3 64 R 3 67 R 3 75 Y 3 83 Y 3 95 Y 4 7 B ...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 155ms
memory: 77240kb
input:
100 610 89 75 83 1 22 Y 1 23 B 1 26 Y 1 34 B 1 42 R 1 44 B 1 50 R 1 58 Y 1 65 B 1 70 B 1 88 X 1 92 R 1 100 R 2 19 R 2 31 B 2 42 Y 2 44 B 2 48 B 2 49 B 2 57 Y 2 75 R 2 88 Y 2 97 B 3 23 Y 3 26 R 3 27 Y 3 46 R 3 54 R 3 55 R 3 57 R 3 62 Y 3 63 B 3 67 Y 3 75 R 3 76 R 3 79 R 3 80 B 3 94 B 3 98 Y 3 99 B 3 ...
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 2ms
memory: 4956kb
input:
100 745 3 80 69 1 2 P 1 4 G 1 10 P 1 25 G 1 27 P 1 30 O 1 32 G 1 38 G 1 40 G 1 48 P 1 66 G 1 88 P 1 92 G 1 99 G 1 100 G 2 3 P 2 7 P 2 25 O 2 29 O 2 31 X 2 37 O 2 45 P 2 58 O 2 63 O 2 74 O 2 80 G 2 83 O 2 93 P 2 94 P 2 96 G 3 18 G 3 23 G 3 29 P 3 37 P 3 43 G 3 48 P 3 54 O 3 57 G 3 58 O 3 62 G 3 69 P ...
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 2ms
memory: 4364kb
input:
100 536 85 85 11 1 14 G 1 15 O 1 16 G 1 23 G 1 24 O 1 36 P 1 55 P 1 77 P 1 82 O 1 98 G 2 17 O 2 28 P 2 36 G 2 53 G 2 58 O 2 64 P 2 65 O 2 68 P 2 75 P 2 92 G 2 99 P 3 5 G 3 30 G 3 48 G 3 57 G 3 59 G 3 85 G 3 88 G 4 16 G 4 33 O 4 35 O 4 52 O 4 61 P 4 74 G 4 75 O 4 90 O 4 94 P 5 12 G 5 28 O 5 31 O 5 45...
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 125ms
memory: 66464kb
input:
100 537 76 96 63 1 2 P 1 9 Y 1 11 B 1 26 G 1 34 G 1 80 G 1 82 X 1 84 R 1 88 P 1 96 G 2 7 B 2 18 B 2 29 B 2 30 B 2 31 X 2 54 P 2 79 P 2 84 R 2 88 O 3 7 G 3 19 G 3 21 R 3 26 X 3 40 G 3 49 B 3 54 B 3 60 G 3 74 R 3 81 R 3 87 G 3 92 P 3 95 O 3 98 P 4 8 Y 4 18 Y 4 20 G 4 40 R 4 48 B 4 53 X 4 88 R 4 92 O 5...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 115ms
memory: 50868kb
input:
100 535 85 24 55 1 7 G 1 17 R 1 23 B 1 24 O 1 30 R 1 33 P 1 43 R 1 47 Y 1 63 Y 1 64 B 1 84 P 1 88 O 1 90 R 2 6 B 2 15 O 2 37 B 2 47 R 2 51 O 2 54 G 2 75 G 2 76 G 2 77 R 2 93 G 2 98 Y 3 29 Y 3 40 P 3 48 Y 3 56 Y 3 59 G 3 66 O 3 71 Y 3 89 Y 4 20 P 4 31 R 4 48 B 4 55 R 4 60 P 4 69 O 4 76 P 4 78 B 4 79 ...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 685ms
memory: 82784kb
input:
100 4950 79 56 22 1 2 R 1 3 Y 1 4 R 1 5 B 1 6 R 1 7 B 1 8 R 1 9 Y 1 10 B 1 11 Y 1 12 Y 1 13 R 1 14 Y 1 15 Y 1 16 B 1 17 B 1 18 Y 1 19 R 1 20 Y 1 21 Y 1 22 Y 1 23 B 1 24 B 1 25 R 1 26 Y 1 27 B 1 28 R 1 29 Y 1 30 Y 1 31 B 1 32 R 1 33 B 1 34 Y 1 35 R 1 36 Y 1 37 Y 1 38 Y 1 39 Y 1 40 Y 1 41 Y 1 42 Y 1 4...
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 797ms
memory: 82644kb
input:
100 4950 90 37 69 1 2 R 1 3 R 1 4 Y 1 5 R 1 6 B 1 7 R 1 8 B 1 9 B 1 10 B 1 11 B 1 12 Y 1 13 B 1 14 Y 1 15 R 1 16 R 1 17 B 1 18 Y 1 19 R 1 20 X 1 21 R 1 22 Y 1 23 B 1 24 B 1 25 B 1 26 B 1 27 Y 1 28 R 1 29 B 1 30 R 1 31 B 1 32 Y 1 33 Y 1 34 R 1 35 X 1 36 B 1 37 B 1 38 R 1 39 B 1 40 R 1 41 B 1 42 Y 1 4...
output:
1
result:
ok single line: '1'
Test #21:
score: 0
Accepted
time: 485ms
memory: 78964kb
input:
100 4950 67 36 13 1 2 P 1 3 G 1 4 G 1 5 O 1 6 O 1 7 O 1 8 G 1 9 P 1 10 O 1 11 O 1 12 G 1 13 G 1 14 O 1 15 G 1 16 O 1 17 G 1 18 O 1 19 P 1 20 P 1 21 G 1 22 P 1 23 G 1 24 P 1 25 P 1 26 O 1 27 O 1 28 G 1 29 P 1 30 P 1 31 P 1 32 G 1 33 G 1 34 G 1 35 P 1 36 O 1 37 G 1 38 O 1 39 G 1 40 P 1 41 P 1 42 P 1 4...
output:
1
result:
ok single line: '1'
Test #22:
score: 0
Accepted
time: 3ms
memory: 4508kb
input:
100 4950 84 52 84 1 2 P 1 3 O 1 4 G 1 5 O 1 6 G 1 7 G 1 8 O 1 9 G 1 10 P 1 11 P 1 12 O 1 13 G 1 14 G 1 15 O 1 16 G 1 17 P 1 18 O 1 19 G 1 20 G 1 21 P 1 22 G 1 23 O 1 24 P 1 25 G 1 26 O 1 27 G 1 28 P 1 29 P 1 30 G 1 31 P 1 32 P 1 33 G 1 34 O 1 35 P 1 36 O 1 37 G 1 38 G 1 39 P 1 40 G 1 41 O 1 42 O 1 4...
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 493ms
memory: 82468kb
input:
100 4440 13 45 76 1 2 R 1 3 P 1 4 Y 1 5 P 1 6 B 1 7 O 1 8 G 1 9 B 1 10 O 1 11 R 1 12 R 1 14 P 1 15 R 1 16 O 1 17 Y 1 18 R 1 19 G 1 20 B 1 21 O 1 22 Y 1 23 R 1 24 P 1 25 P 1 26 Y 1 28 Y 1 30 O 1 31 P 1 33 G 1 35 B 1 36 B 1 37 B 1 39 P 1 40 P 1 41 G 1 42 Y 1 43 B 1 44 O 1 45 R 1 46 G 1 47 B 1 48 B 1 4...
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 538ms
memory: 82500kb
input:
100 4462 53 92 78 1 2 R 1 3 Y 1 4 P 1 6 X 1 7 P 1 8 Y 1 9 X 1 10 P 1 11 G 1 12 B 1 13 P 1 14 P 1 15 O 1 16 G 1 17 R 1 19 Y 1 20 Y 1 21 O 1 22 Y 1 23 Y 1 24 O 1 26 Y 1 27 B 1 28 B 1 29 G 1 30 O 1 31 G 1 32 Y 1 33 G 1 34 O 1 35 Y 1 36 X 1 37 G 1 38 R 1 39 X 1 40 G 1 41 G 1 42 R 1 43 B 1 45 G 1 46 Y 1 ...
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 2ms
memory: 4412kb
input:
100 148 1 1 1 1 2 P 1 3 Y 2 3 Y 2 4 O 2 5 B 4 5 B 4 6 G 4 7 R 6 7 R 6 8 P 6 9 Y 8 9 Y 8 10 O 8 11 B 10 11 B 10 12 G 10 13 R 12 13 R 12 14 P 12 15 Y 14 15 Y 14 16 O 14 17 B 16 17 B 16 18 G 16 19 R 18 19 R 18 20 P 18 21 Y 20 21 Y 20 22 O 20 23 B 22 23 B 22 24 G 22 25 R 24 25 R 24 26 P 24 27 Y 26 27 Y ...
output:
1
result:
ok single line: '1'
Test #26:
score: 0
Accepted
time: 351ms
memory: 81448kb
input:
100 4950 23 31 19 1 4 R 4 7 R 7 10 R 10 13 R 13 16 R 16 19 R 19 22 R 22 25 R 25 28 R 28 31 R 31 34 R 34 37 R 37 40 R 40 43 R 43 46 R 46 49 R 49 52 R 52 55 R 55 58 R 58 61 R 61 64 R 64 67 R 67 70 R 70 73 R 73 76 R 76 79 R 79 82 R 82 85 R 85 88 R 88 91 R 91 94 R 94 97 R 97 100 R 3 100 R 3 6 R 6 9 R 9 ...
output:
1
result:
ok single line: '1'
Test #27:
score: 0
Accepted
time: 698ms
memory: 82524kb
input:
100 4950 23 55 69 1 4 R 4 7 R 7 10 R 10 13 R 13 16 R 16 19 R 19 22 R 22 25 R 25 28 R 28 31 R 31 34 R 34 37 R 37 40 R 40 43 R 43 46 R 46 49 R 49 52 R 52 55 R 55 58 R 58 61 R 61 64 R 64 67 R 67 70 R 70 73 R 73 76 R 76 79 R 79 82 R 82 85 R 85 88 R 88 91 R 91 94 R 94 97 R 97 100 R 3 100 R 3 6 R 6 9 R 9 ...
output:
1
result:
ok single line: '1'
Test #28:
score: 0
Accepted
time: 21ms
memory: 7180kb
input:
99 1584 29 62 91 1 2 R 1 3 R 1 4 R 1 5 R 1 6 R 1 7 R 1 8 R 1 9 R 1 10 R 1 11 R 1 12 R 1 13 R 1 14 R 1 15 R 1 16 R 1 17 R 1 18 R 1 19 R 1 20 R 1 21 R 1 22 R 1 23 R 1 24 R 1 25 R 1 26 R 1 27 R 1 28 R 1 29 R 1 30 R 1 31 R 1 32 R 1 33 R 2 3 R 2 4 R 2 5 R 2 6 R 2 7 R 2 8 R 2 9 R 2 10 R 2 11 R 2 12 R 2 13...
output:
1
result:
ok single line: '1'
Test #29:
score: 0
Accepted
time: 8ms
memory: 5644kb
input:
100 1200 5 40 67 1 2 R 1 3 R 1 4 R 1 5 R 1 6 R 1 7 R 1 8 R 1 9 R 1 10 R 1 11 R 1 12 R 1 13 R 1 14 R 1 15 R 1 16 R 1 17 R 1 18 R 1 19 R 1 20 R 1 21 R 1 22 R 1 23 R 1 24 R 1 25 R 2 3 R 2 4 R 2 5 R 2 6 R 2 7 R 2 8 R 2 9 R 2 10 R 2 11 R 2 12 R 2 13 R 2 14 R 2 15 R 2 16 R 2 17 R 2 18 R 2 19 R 2 20 R 2 21...
output:
1
result:
ok single line: '1'
Test #30:
score: 0
Accepted
time: 2ms
memory: 4404kb
input:
99 120 1 2 3 3 4 Y 1 4 R 4 5 O 5 6 Y 5 7 R 2 8 B 6 8 Y 8 9 G 9 10 B 9 11 Y 10 12 B 7 12 R 12 13 P 13 14 B 13 15 R 11 16 Y 15 16 R 16 17 O 17 18 Y 17 19 R 19 20 R 14 20 B 20 21 P 21 22 R 21 23 B 23 24 B 18 24 Y 24 25 G 25 26 B 25 27 Y 22 28 R 27 28 Y 28 29 O 29 30 R 29 31 Y 30 32 R 26 32 B 32 33 P 33...
output:
1
result:
ok single line: '1'