QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791738#8130. Yet Another Balanced Coloring ProblemrizynvuRE 1ms8504kbC++141.3kb2024-11-28 20:37:442024-11-28 20:37:53

Judging History

你现在查看的是最新测评结果

  • [2024-11-28 20:37:53]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:8504kb
  • [2024-11-28 20:37:44]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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 ...

output:


result: