QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791745#8130. Yet Another Balanced Coloring ProblemrizynvuWA 9ms9440kbC++141.3kb2024-11-28 20:39:502024-11-28 20:39:51

Judging History

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

  • [2024-11-28 20:39:51]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:9440kb
  • [2024-11-28 20:39:50]
  • 提交

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 < m; 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: 2ms
memory: 9228kb

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
Wrong Answer
time: 9ms
memory: 9440kb

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:

BRBR
BBRRB
BRRBRB
BBR
BRBRB
BBRRB
BBRR
BRBR
BBRBRBR
BRBRBRB
BRB
BRBRBR
BBR
BRRBRBB
BBBRRR
BRBR
BBR
BRRRB
BBR
BRRBB
BBRRB
BRBR
BRRBB
BBR
BRBRB
BBRR
BRRBRB
BBRRBR
BRBR
BBRRRB
BRRRBB
BRRBB
BRBRBR
BRRBRB
BRRRBB
BRB
BRRB
BBR
BBR
BRRBR
BRRB
BBRBRR
BBR
BRRBR
BRB
BRBRBR
BRBRBR
BBR
BBRBRR
BBR
BRB
BBRR
BRRBB
...

result:

wrong answer charge of vertex 8 in tree 2 violates range (test case 20)