QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #395017 | #3606. Painted Corridors | Zuqa | AC ✓ | 3348ms | 148708kb | C++20 | 2.5kb | 2024-04-21 01:05:16 | 2024-04-21 01:05:17 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned uint;
typedef __int128 bint;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937_64 for unsigned long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int N = 1e2 + 5;
set<int> st;
int vis[N][N][N];
vector<tuple<int, int, int>> G[N];
void dfs(int r, int b, int y, int e = -1)
{
if(~e)
st.insert(e);
if(vis[r][b][y])
return;
vis[r][b][y] = 1;
for(auto &[v, id, msk]: G[r])
{
if(msk == 0)
dfs(v, b, y);
else if(msk == 1)
dfs(v, b, y, id);
else if(msk == 3 && r == b)
dfs(v, v, y, id);
else if(msk == 5 && r == y)
dfs(v, b, v, id);
}
for(auto &[v, id, msk]: G[b])
{
if(msk == 0)
dfs(r, v, y);
else if(msk == 2)
dfs(r, v, y, id);
else if(msk == 6 && b == y)
dfs(r, v, v, id);
}
for(auto &[v, id, msk]: G[y])
{
if(msk == 0)
dfs(r, b, v);
else if(msk == 4)
dfs(r, b, v, id);
}
}
void doWork()
{
int n, m;
cin >> n >> m;
char c;
int r, b, y;
int cnt = 0;
cin >> r >> b >> y;
for(int i = 0, u, v, msk; i < m; i++)
{
cin >> u >> v >> c;
if(c == 'X')
msk = 0;
else if(c == 'R')
msk = 1;
else if(c == 'B')
msk = 2;
else if(c == 'Y')
msk = 4;
else if(c == 'G')
msk = 6;
else if(c == 'P')
msk = 3;
else
msk = 5;
cnt += (msk != 0);
G[u].push_back({v, i, msk});
G[v].push_back({u, i, msk});
}
dfs(r, b, y);
cout << (st.size() == cnt);
}
signed main()
{
FIO
int T = 1;
// cin >> T;
for(int i = 1; i <= T; i++)
doWork();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
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: 0ms
memory: 3572kb
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: 0ms
memory: 3708kb
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: 0ms
memory: 3772kb
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: 3636kb
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: 0ms
memory: 3712kb
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: 3648kb
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: 0ms
memory: 3652kb
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: 3664kb
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: 0ms
memory: 3788kb
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: 0ms
memory: 3628kb
input:
100 1 10 20 30 77 88 X
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3572kb
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: 401ms
memory: 137360kb
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: 303ms
memory: 130988kb
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: 5ms
memory: 8228kb
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: 0ms
memory: 4604kb
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: 209ms
memory: 110448kb
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: 213ms
memory: 91764kb
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: 3348ms
memory: 148708kb
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: 3009ms
memory: 139124kb
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: 603ms
memory: 98044kb
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: 2ms
memory: 4840kb
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: 1660ms
memory: 148688kb
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: 1635ms
memory: 138272kb
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: 1ms
memory: 4028kb
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: 787ms
memory: 146732kb
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: 774ms
memory: 148332kb
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: 61ms
memory: 9424kb
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: 21ms
memory: 6328kb
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: 1ms
memory: 4148kb
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'