QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#448202 | #8680. Turning Red | james1BadCreeper# | AC ✓ | 305ms | 79460kb | C++17 | 1.7kb | 2024-06-19 14:07:46 | 2024-06-19 14:07:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 8e5 + 5;
int n, m, cnt[N], vis[N];
char a[N];
vector<int> G[N];
int main(void) {
ios::sync_with_stdio(0);
cin >> n >> m >> a + 1;
for (int i = 1; i <= n; ++i)
if (a[i] == 'R') a[i] = 0;
else if (a[i] == 'G') a[i] = 1;
else a[i] = 2;
for (int i = 1; i <= m; ++i) {
int k; cin >> k;
while (k--) {
int x; cin >> x;
G[i].emplace_back(x + m);
G[x + m].emplace_back(i);
}
}
for (int i = 1; i <= n; ++i)
if (!G[i + m].size() && a[i]) return cout << "impossible\n", 0;
int ans = 0;
for (int i = 1; i <= m; ++i) if (!vis[i]) {
int mn = 1e9;
vector<int> now;
bool flg = 1;
auto dfs = [&](auto &&self, int x) -> void {
vis[x] = 1; now.emplace_back(x);
if (x <= m) {
for (int y : G[x])
if (vis[y] != 1) self(self, y);
} else {
int s = a[x - m], p = 0;
for (int y : G[x])
if (vis[y] != 1) p = y;
else s += cnt[y];
if (p) cnt[p] = (3 - s % 3) % 3, self(self, p);
else if (s % 3 != 0) flg = 0;
}
};
for (cnt[i] = 0; cnt[i] < 3; ++cnt[i]) {
flg = 1; dfs(dfs, i); int s = 0;
if (flg) { for (int j : now) if (j <= m) s += cnt[j]; mn = min(mn, s); }
for (int j : now) vis[j] = 2; now.clear();
}
if (mn == 1e9) return cout << "impossible\n", 0;
ans += mn;
}
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 68ms
memory: 36224kb
input:
200000 171004 RGRGBBBGGBRRRBBRRBRBBGRRRGGGGRRRRGBBBRGGGBGGRGGRGRRBRBRRGGBGGGGBRBRBRRBRBRGRRGRBRRBGRRRRBRBBBRGBBBGRRBRGRRGGRGGBGRBGRBRGBBRRBBBGBGRGBBRBGGGGBBBBRBRRRGBGRRBBGGGRRBRBBRGRBGRBRGGBRBBBBRGGRRRBGRBGRBRRRGRGRRBRGRRGRRGBBBBRGGBBRRBGGBGBGRBRGBGGRRGRBRRGGRGRBBBRRBBRRGGRRRRGBRGGGGGGRGBRGRBBBGRBBG...
output:
impossible
result:
ok single line: 'impossible'
Test #2:
score: 0
Accepted
time: 2ms
memory: 22592kb
input:
10 0 RRRRRRRRRR
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 23980kb
input:
10 0 GGGGGGGGGG
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 24000kb
input:
10 0 BBBBBBBBBB
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 3ms
memory: 22620kb
input:
10 0 RGBRGBRGBR
output:
impossible
result:
ok single line: 'impossible'
Test #6:
score: 0
Accepted
time: 0ms
memory: 22744kb
input:
10 0 GBBRRRBRGB
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 0ms
memory: 24492kb
input:
10 2 BBRRBRBRRR 7 7 8 5 3 10 9 4 5 6 10 1 3 2
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 4ms
memory: 24396kb
input:
10 9 RRRRRBGRRG 1 10 5 9 3 8 2 5 2 8 7 1 7 1 10 2 6 1 1 3 1 6 4 1 9 4 2
output:
5
result:
ok single line: '5'
Test #9:
score: 0
Accepted
time: 52ms
memory: 32116kb
input:
200000 10000 RBBBBGRRGGRBRGRGBBRBGGRGRGRBBRRRGRGRGRBGRBBBBGBGBBGGBBGGGGBRGBBBBBBRRGBBGGGRBBBGBRGGGRRGGGGBGBGBGRBBGGRRRGGGRGGRBRRBGRGRBBGBGGRGBBRBBBGGRGBBGBBBBBGRGBGGRGBGGBGRRBGBBGRBGBGGRBBBGBBBGGGBBBRBBGRRRBGBBRBRBBGRGGGBBRGRRRGRRRRGRRBGBRRRRGBBRBBGRRRRBRBRRRGBGRGGBGRBRBGBBRRGBBRBBBGBGGGBBRGRBRRGBBR...
output:
impossible
result:
ok single line: 'impossible'
Test #10:
score: 0
Accepted
time: 59ms
memory: 32020kb
input:
200000 49974 GRBRRGBRRRRRGBRBGRRBGGGRRRRBGGBBBGRRGBBRBGBRBRRBRBBRGRBGGBBGBBRRRBGGBRBRRGBRRRBRRGRGRGRBGRBGBBBGGGRGRBGRGGRBBRBRGGBRBBRRGGGRBGBGBGRBRBRGGBBBRBBRGRRBBGBGRBBRBBBRGGGGRRBGBBRGBGBGGBRBGGRGGGBRRRBBBGRRRRGBBBGBBGRRRBGRGGGRGBRGBGRBBRBRRBGGRGBBRGBBBRGRBBBRRGGRRRGGRRRGRRBGGGBGRRGBRRRRRGRGBGGRRRR...
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 63ms
memory: 32472kb
input:
200000 97963 GRBBRBGGGBGBBGRBBBRGRGBBBGBRBGBGGGBRBBGRGRRBRRGBRRBBGRRGBRRGBBRBGRRRGRGRRRBGBBRGGBRRBBBGRBBGBBRRRGRRGRGRRRBBRGBRRRRRGGGGGBGRRBGRGGBBBBRBBRBBBBBBRRRGBGGRGRGRBBRRBGBRRBBRGBGRBRBRGBRRGBRBGGRGGGGBGGGRBBRGRGGBBGRRGRBGGRBGRBBBRRGGRGGBRRBBRGGRBRBBGRRRGGGBRBRGBRBRBBGGBRGRBBRGGBBBGGBGRRRRRRGGGBR...
output:
impossible
result:
ok single line: 'impossible'
Test #12:
score: 0
Accepted
time: 76ms
memory: 47312kb
input:
200000 400000 GRGBBBRRGGRGBBRBBGBRRRBBRBRGRGRRBBRBRGRBRGGRRGGBRGRRBRBRRBRRGGBBGRBBGRRRBRBGBBRBGBRBBBBBBGBRGRBBGRGBGBBGRGBGBBBBGRGRRRGGGBGGGGRBRBRBRRBGGBGRRGBGGGRRBBBGRBRBGGBBRBBGRGGBGRGBGRRGGBRGGRGRGGBGBRBBBRGGBRRRRBGRBGRRGBRBRGRRBBGGGRRGRGGBRBBBBRGBBGRGGBGGRBGGRBRBBRBBBGRGGGGGBGGRRBBGRGGGRGBRBGGGGR...
output:
200051
result:
ok single line: '200051'
Test #13:
score: 0
Accepted
time: 3ms
memory: 26088kb
input:
10 10 GRBBGBBRRG 2 10 1 2 9 10 2 5 6 2 4 2 2 8 4 2 7 5 2 2 3 2 3 7 2 6 9 1 1
output:
12
result:
ok single line: '12'
Test #14:
score: 0
Accepted
time: 229ms
memory: 67976kb
input:
200000 199999 BRGBBBRBBGGRRGBGRBGBRRGGGBRGGBBGRRRGGBRBBGRBGGBGRGBGBRBGGRBRRGBRBGRBGGGRRGGBGGBBBBBRRGRRRRBGRBGGGBBGGGRGRRGRGRGBGRBBBGGRGRRRRGRGGGGGGGBBBBGRGRGGRBRGRGBBBRRBGRGRGGBGRBRRRRGBBRBBGBGRRRGBRRRBRRGBBBRRBGRBRRBGBGBGGRBBRRGGRRRBBRRGBRGRRGBRRGRRGGRGRRRRGBGRBBRRGRRBRRBBRGBRRBRGGRRBBBRGRGBBGGBRRR...
output:
199855
result:
ok single line: '199855'
Test #15:
score: 0
Accepted
time: 278ms
memory: 79124kb
input:
200000 199999 BRGGGBBBGGRBGGBRGGGBBBBBBBRRGBBBGBBRBGGBGGGBGBBGBBGRBRRGGRRBBGGBRRGBRGBBBGGGRBRRRBRBBBRGBRRBRRGBGBRGBGRGGGGBBRGGRRGBGGBBGBBRBGRRBRBRGGBBRRRGBBGRRBRRBRGGGBBGGRGRGGGBGGGRBRGGRBGGGGBBRBRRBRRGRBBRBGGBBBGRGRBGRRBGGRRRBRBRGGGBGGRBGBBBRGGRRRRBGRGRBGGRBGBBBGBBRRRGGRGBRRRBRGRRRGGGRRRBGRRGGRBRBR...
output:
impossible
result:
ok single line: 'impossible'
Test #16:
score: 0
Accepted
time: 305ms
memory: 75320kb
input:
200000 200000 RRBBBGRBBGRBGBBRRGGBRBBGGBRGRBGBGBBBRBBGGBGRGBBRBRGBGRRGBBBGBGRRRBGRGBBGBBRGBRGBGGBBGBRRRRRRBBRBGGBGGRBBRBBBRBBBRRRGGGGRGBBBRBBGRRBRBBRBBGGRRRGGBRGRRRGRBBRGGGGRBGGBBGGRRRBGBBGBBRGRBRGRBGBRBGBGGGBBGGRBRRGBBRRGRBGBRBRRBBGGBGGRBGRGGGRRGGBGRRBBRBRRGGBRGGRGRBBRRRRBBRBGRBBBRGGGRGRGBGRGRGBRGR...
output:
199859
result:
ok single line: '199859'
Test #17:
score: 0
Accepted
time: 234ms
memory: 63736kb
input:
200000 200000 RRRRBRRGGGGGGRBBBGRRGBBRRBGRRBRRGRRBGGRGBRBGBRGGBRRBBGGGRGRGRGBGRBRGRBBGBRRBRRBGGGRBGBRGBBGGRGBRGGRBGBGGRBGGRGGGGRGGGGRRRGBBGRBRRGBRRBGRBBBRRBGRGRGBBGRRBBRBBGGRBRBGRBGBGBRRGGGBBGGBGRRGRRBGGBBRGGBRGRGBGGGRBBBRGRRGRBGRRGGGRBRGGGGRRGGRGGRBGRGBRBGBBRGBGRGBBBGRRGRGGBBBRBGGRGBRGRBGRRRRBBGRGR...
output:
200292
result:
ok single line: '200292'
Test #18:
score: 0
Accepted
time: 6ms
memory: 24660kb
input:
10 9 BRBRBRGRRB 1 8 1 4 1 6 1 9 1 3 1 7 10 2 5 6 4 1 7 8 9 3 10 1 5 1 2
output:
12
result:
ok single line: '12'
Test #19:
score: 0
Accepted
time: 104ms
memory: 43416kb
input:
200000 199999 BRRGBGBBGRGBGRGRGRBRRGBGBRRGBBBRGBBBRBBRRRGRRRBBRBGGRRGBBBGRRRBBBRBBRRBRRBBBGGGBRRRBRBGRBGRBRGGBGRBRGGGBGRGRGBBBRGGRRRBBBGBGGRRGRBRBBBBRRGBGRBRBGRGBRGRGRBRBGRGBRBRGBBBRGGGGGBRRGBRBBBGBRGRRGBRBGBBRBGGRGRGBBGRGRBGRRGBRGRBGRBBRBGRBRBRRBBBGGGBBGGBGBGGBGBBRRGGGGRBRBGBGBBGRBGRGRBBBBRGRGBBGRG...
output:
200007
result:
ok single line: '200007'
Test #20:
score: 0
Accepted
time: 110ms
memory: 41676kb
input:
200000 199999 RBRGBRGRRGRBGGBGRRRGBGRBRRBGGBRBGBRGRGRRRBBRRRRRRGGBBGRGRGBGRGRBBBRBGRBBGGGRBBRRGBRGGRRGBRGGRBRRRGRGRRRBGRRRBRGBRBBBRGGRGRRGGRBGGRBRRGBGGGBGGBRGBGGBBRRBRRRRGBBBRGBRBGBBGRBRGGBBBBRGRGGBRBRRGGBRGBGBRBGBGBGGBRRGRGGRRGRBRRRBGGBGRBGRGRGGGBRGRGRRBBGRBRGRRGGBGRRBGGGRRRBGRBGRGRBBRGBBGBGRRGRBGG...
output:
impossible
result:
ok single line: 'impossible'
Test #21:
score: 0
Accepted
time: 0ms
memory: 25804kb
input:
10 10 BRBBRGBGRG 2 10 6 2 8 9 2 7 1 2 2 4 2 6 7 2 5 10 2 9 3 2 2 5 2 1 8 2 3 4
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 276ms
memory: 79460kb
input:
200000 200000 RRGBBGRGBGGRBRBRRRBGGBBGGBGRBGBGRRBRRBBGBBGBBGGGGBBGBRRRGBRRBRBGGGRBRRGBGRRGBGGBBGRBRRBGBRGBBBBGGRRRGBGGBBBBRRBBGBBBBGGGRGRGBBBRRGBGRBGRBRGRRRBBRGGRRBBGRRGGGBBBBBRGGRBGBGGGGGGGRGGRRBGGBBBBBRGRRBBBRRGGGBGRGRGGRBGRRBGBBRBGRGBBGRGBBGRGGRGRRRBGGGRRBRGRGGRRGRGBBBGBGBBBBBRGBBBRBGGGGGBRGBBBRG...
output:
impossible
result:
ok single line: 'impossible'
Test #23:
score: 0
Accepted
time: 250ms
memory: 78092kb
input:
200000 200000 RRRGGRBRRBBRBBGBGGGBBBGGBGRRGRGBBGBGBRBRGGGBGRGRGGBGGGRBRRGBGGBRGRBBBBBRGRRRRBRRRBRRRGRGRBBGRGGBGBRRBGRRGRGRBGGRBRBBRRBBBBBBBBGBBBRGBGRRBRGBBBBRGBBBRGBGGRBRRBBRGRGGRRGGRRGGBRGBBGRGGGGRBRGRGGBGRRGGBBBGRGBBBBGBGRBGBBBBBRRRGRGBBBBBBRRBGRRBRRBGGBRRGBBRRBRBRBRBBBGGRBBGRRGRBGRRBGBGRBRBRRRGGR...
output:
impossible
result:
ok single line: 'impossible'
Test #24:
score: 0
Accepted
time: 32ms
memory: 29200kb
input:
60000 50000 BRGGGRGRRGGGGBBBGGBGRGGRGBGBGRGBBBBRGGRBRBGRBRGBGRBBRRRBRRGGRGBBBRGRBRBRBRBBBBGBGRGGBRRGGBGBGBGBGBGGRBRRGRRGBGGGBBRBBGGGRRGRBBBBBGGBBGRBBBGBGGRRRRRGRBGRRRRBGRBRRBBGRRBGRBGRGGGGBBGGRGRBGRRRRRGGRRBRRRBRBRBRBBRGBRGBRRBRGBGBRRGRBRBRRRBBGGRGGRRBGRRBBGGBRRBBBBRRRGBRRBRBRGGBGBGGGGBBGGGRBGRGRGBB...
output:
30280
result:
ok single line: '30280'
Test #25:
score: 0
Accepted
time: 22ms
memory: 28940kb
input:
54937 54937 GGGRGBGRRRRRBGBBRGRBBGBGBRRRBBGGBGGRBBGRBRGBGRBBGGGRBBGGGBRGRGRRRGRRGGGBGGRBRBGBGRGRGRGGGBGRRBRBGBBBGRRRGBRBGGGGGRBGGGRRGRRBBGGGGGBRGBBGGRBGRGRBRGBRRGGRGGBRRBGRBRRBBGGGRBGBRRRRBGBGRRBRGBRRRBRRGGRRGBBGBBGBGRGGRBRGRGRBGBGGRRRRGGGRGGRGRRGBGRBBGBRBGBRGGBBGBGGBRBBGBBBGGRRGGBBBBRRBGRGGRRBGRRRR...
output:
54911
result:
ok single line: '54911'
Test #26:
score: 0
Accepted
time: 72ms
memory: 46456kb
input:
200000 400000 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 80ms
memory: 46776kb
input:
200000 400000 GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...
output:
400000
result:
ok single line: '400000'
Test #28:
score: 0
Accepted
time: 72ms
memory: 46476kb
input:
200000 400000 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
output:
200000
result:
ok single line: '200000'
Test #29:
score: 0
Accepted
time: 46ms
memory: 30128kb
input:
200000 10 BBBRBBBRRGRBRRRRBGBRBRRRGBBBRGRGGGGRGBGGGGRGRBBGGRGBBBRRRBBRBGGRRGBBRRRRGRRBGGRBBGBBBGBGGRGRGGGRRGGRRBRBGGRBBRBRRGRRRGGRGBBRRBGRGRBRRRGRBRRGRGBBRGGBBBRBBRRBGBGRBGGBBGGBBGRBGGBBGBRRRGBRBGRGBBBRBRBRBBRRRGBGBRRGRRRBGBGGGRGBGGGGRBGBBBRRGRGBRGRGRRGRGRBGBGGBGGGBRGRBBBBRBRBRBBGGBRRRGBGBGRRRGBBRRG...
output:
impossible
result:
ok single line: 'impossible'
Extra Test:
score: 0
Extra Test Passed