QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791738 | #8130. Yet Another Balanced Coloring Problem | rizynvu | RE | 1ms | 8504kb | C++14 | 1.3kb | 2024-11-28 20:37:44 | 2024-11-28 20:37:53 |
Judging History
answer
#include<bits/stdc++.h>
constexpr int maxn = 2e5 + 10, maxm = 5e5 + 10;
std::vector<std::pair<int, int> > to[maxn];
int st[maxm];
void dfs(int u) {
if (to[u].empty()) return ;
auto [v, w] = to[u].back(); to[u].pop_back();
if (st[w]) dfs(u);
else st[w] = u, dfs(v);
}
inline void solve() {
int n, m;
scanf("%d%d", &n, &m);
int l = 0;
for (int i = 1; i <= n + m + 1; i++) to[i].clear();
for (int i = 1, f; i < n; i++) {
scanf("%d", &f), st[++l] = 0;
to[i].emplace_back(f, l), to[f].emplace_back(i, l);
}
for (int i = 1, f; i < n; i++) {
scanf("%d", &f), st[++l] = 0;
to[n + i].emplace_back(n + f, l), to[n + f].emplace_back(n + i, l);
}
int pl = l + 1;
for (int i = 1; (int)to[i].size() == 1; i++) {
st[++l] = 0;
to[i].emplace_back(n + i, l), to[n + i].emplace_back(i, l);
}
int pr = l;
for (int i = 1; i <= n + m; i++) {
if (to[i].size() % 2 == 1) {
st[++l] = 0;
to[i].emplace_back(n + m + 1, l), to[n + m + 1].emplace_back(i, l);
}
}
assert(to[n + m + 1].size() % 2 == 0);
for (int i = 1; i <= n + m; i++) dfs(i);
for (int i = pl; i <= pr; i++) {
putchar("RB"[st[i] <= n]);
}
puts("");
}
int main() {
for (int T, _ = scanf("%d", &T); T--; ) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 8504kb
input:
2 7 7 5 5 6 6 7 7 5 6 5 6 7 7 5 4 4 4 5 5 4 4 4
output:
BRRB BRB
result:
ok ok (2 test cases)
Test #2:
score: -100
Runtime Error
input:
10000 6 6 5 5 5 5 6 5 6 6 6 6 9 6 7 9 7 7 6 8 9 9 6 6 6 6 6 9 8 9 9 8 7 7 8 8 9 7 7 8 7 7 7 8 6 10 4 5 5 6 6 4 6 5 7 8 9 8 9 10 6 9 6 6 6 6 6 6 9 7 8 8 9 9 9 8 9 8 6 6 7 6 7 8 7 9 7 6 7 8 9 9 9 8 6 7 7 5 8 8 8 9 7 5 6 5 8 7 8 8 7 6 6 5 5 6 7 8 5 7 6 6 7 7 9 9 8 9 8 8 8 8 9 9 9 9 8 8 9 9 8 9 9 8 8 8 ...