QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311207#8130. Yet Another Balanced Coloring Problemucup-team484WA 12ms29304kbC++171.4kb2024-01-22 05:53:452024-01-22 05:53:47

Judging History

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

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

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<pair<int, 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]);) {
		auto [v, i] = adj[u][cnt[u]];
		cnt[u]++;
		if (i == -1) 
			continue;
		adj[v][i].second = -1;
		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].emplace_back(p, size(adj[p]));
		adj[p].emplace_back(i, size(adj[i]) - 1);
	}
	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].emplace_back(p + n, size(adj[p + n]));
		adj[p + n].emplace_back(j, size(adj[j]) - 1);
	}
	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();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 29304kb

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: 29128kb

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:

BRRB
RRBBR
RBRRBB
RRB
BRRBR
RRBBR
RRBB
BRRR
RRBRBRB
RBRBRBR
RBR
BRRRBB
RBR
RBRBRBR
RRRBBB
RBRB
RRB
BBRRR
RRB
BBRRR
RRBBR
RBBR
BBRRR
RRB
BRBRR
BBRR
BRBRRB
RRBBRB
BRRB
RBRBRB
BBRBRR
RBBRR
RBRBRB
BRRBRB
RRBBRB
BRR
RBBR
RRB
RBR
BRBRR
RRRB
RRBRBB
RRB
RRBRR
BRR
RBRBRB
BBRRBR
RRR
RBRBRB
RBR
BRR
RBRB
BRRBR
...

result:

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