QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311206#8130. Yet Another Balanced Coloring Problemucup-team484WA 12ms30176kbC++171.3kb2024-01-22 05:40:082024-01-22 05:40:08

Judging History

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

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-22 05:40:08]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:30176kb
  • [2024-01-22 05:40:08]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
vector<int> adj[N];
int cnt[N], ans[N], n, m, k;

void dfs(int u, int p = -1) {
	if (u < k)
		ans[u] = p < n;
	for (; cnt[u] < size(adj[u]);) {
		int v = adj[u][cnt[u]];
		cnt[u]++;
		if (v == p) 
			continue;
		dfs(v, u);
	}
}

void solve() {
	k = N; cin >> n >> m;
	for (int i = 0; i < n + m; i++)
		adj[i].clear(), cnt[i] = ans[i] = 0;
	vector<int> deg(n + m);
	for (int i = 0; i + 1 < n; i++) {
		int p; cin >> p; p--;
		k = min(k, p);
		if (i >= k && deg[i] % 2 == 0)
			continue;
		deg[p]++;
		adj[i].push_back(p);
		adj[p].push_back(i);
	}
	for (int i = 0; i + 1 < m; i++) {
		int p; cin >> p; p--;
		int j = i < k ? i : i + n;
		if (j >= k && deg[j] % 2 == 0)
			continue;
		deg[p + n]++;
		adj[j].push_back(p + n);
		adj[p + n].push_back(j);
	}
	if (adj[n + m - 1].empty())
		dfs(k);
	else
		dfs(n + m - 1);
	string s(k, 'R');
	for (int i = 0; i < k; i++)
		if (ans[i])
			s[i] = 'B';
	cout << s << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t; cin >> t; while (t--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 29708kb

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
RBR

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 12ms
memory: 30176kb

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:

BBBR
RRRBR
RBRRBR
RRB
BBRBR
RRBBR
RRBB
BRRR
RRBRRRB
RBRBRBR
RBR
BRRBRB
RBR
RBRBRBR
RRRBRB
RBRB
RRB
BBBBR
RRB
BBBRR
RRBBR
RBRR
BBBBR
RRB
BRBRB
BBRR
BRBRBR
RRRBRB
BRRB
RBBBBB
BBRBRB
RBBBR
RBRBRB
BRBRBR
RRRBRB
BRR
RBBR
RRB
RBR
BBBRB
RRRB
RRBRBR
RRB
RRBRR
BRR
RBRBRB
BBRBRR
RRR
RBRBRB
RBR
BRR
RRRB
BRBRB
...

result:

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