QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791809#8130. Yet Another Balanced Coloring ProblemrizynvuWA 9ms13908kbC++141.2kb2024-11-28 21:04:432024-11-28 21:04:44

Judging History

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

  • [2024-11-28 21:04:44]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:13908kb
  • [2024-11-28 21:04:43]
  • 提交

answer

#include<bits/stdc++.h>
constexpr int maxn = 2e5 + 10;
std::vector<int> son[maxn], to[maxn];
int k, pr[maxn];
void dfs(int u) {
   if (son[u].empty()) {
      pr[u] = u, k++;
   } else {
      for (int v : son[u]) {
         dfs(v);
         if (pr[u] && pr[v]) {
            to[pr[u]].push_back(pr[v]);
            to[pr[v]].push_back(pr[u]);
            pr[u] = 0;
         } else {
            pr[u] |= pr[v];
         }
      }
   }
}
inline void solve(int n) {
   for (int i = 1; i <= n; i++) son[i].clear();
   for (int i = 1, f; i < n; i++) {
      scanf("%d", &f), son[f].push_back(i);
   }
   dfs(n);
}
int col[maxn];
void dfsc(int u, int c) {
   if (col[u]) return ;
   col[u] = c;
   for (int v : to[u]) {
      dfsc(v, 3 - c);
   }
} 
inline void solve() {
   int n, m;
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i++) to[i].clear();
   k = 0;
   solve(n), solve(m);
   k >>= 1;
   memset(col + 1, 0, sizeof(int) * k);
   for (int i = 1; i <= k; i++) {
      dfsc(i, 1);
      putchar(" RB"[col[i]]);
   }
   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: 0ms
memory: 13484kb

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:

RBBR
RBR

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 9ms
memory: 13908kb

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:

RBRB
RRBBR
RRRBBR
RRB
RBRRB
RBRRB
RRBB
RBBR
RBBRBRB
RBRBRBR
RRR
RRBBBR
RRB
RBRBRBR
RRBBRB
RRRB
RRB
RBBRR
RRB
RBBRB
RBBRR
RBRB
RRBRB
RRB
RRBBR
RRBB
RBRBRB
RBRRBB
RBRR
RBRBRB
RBBRBR
RRBBR
RBRBRB
RBRBRB
RRRRBB
RRB
RRBB
RBR
RRB
RBRBB
RBRB
RBRBRB
RRB
RBBRR
RRB
RBRRBB
RBRBBR
RRR
RRBRBR
RRB
RRB
RBRB
RBRBR
...

result:

wrong answer charge of vertex 7 in tree 1 violates range (test case 3)