QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#646392#8544. Colorful Graph 2Iron_gainerWA 80ms3616kbC++201.4kb2024-10-16 22:40:542024-10-16 22:40:56

Judging History

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

  • [2024-10-16 22:40:56]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:3616kb
  • [2024-10-16 22:40:54]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<array>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
constexpr ll mod = 1e9 + 7;
void speed()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
ll ksm(ll num, ll cnt)
{
	ll temp = 1;
	ll mul = num;
	while (cnt)
	{
		if (cnt & 1) temp = (temp * mul) % mod;
		mul = (mul * mul) % mod;
		cnt >>= 1;
	}
	return temp;
}
vector<int>edge[200005];
void solve()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		edge[u+1].push_back(v+1);
		edge[v+1].push_back(u+1);
	}
	vector<int>is(n + 1);
	queue<int>q;
	for (int i = 1; i <= n; i++)
	{
		if (is[i] == 0)
		{
			q.push(i);
			if (i == 1)
				is[i] = 1;
			else
				is[i] = -is[i - 1];
			while (!q.empty())
			{
				int f = q.front();
				q.pop();
				if (i != f)
				{
					if (is[f] != 0) continue;
				}
				for (auto j : edge[f])
				{ 
					if (!is[j])
					{
						is[j] = -is[f];
						q.push(j);
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (is[i] == 1)
			cout << "R";
		else
			cout << "B";
	}
	cout << endl;
	for (int i = 1; i <= n; i++)
		edge[i].clear();
}
int main()
{
	speed();
	int t;
	cin >> t;
	//t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

RBR
RBRR
RBBRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 80ms
memory: 3616kb

input:

100000
9 6
2 0
4 6
3 6
0 6
0 7
2 6
3 0
5 2
2 4
2 0
6 3
1 5
4 1
2 4
9 6
3 1
6 4
8 1
3 6
1 6
8 6
3 0
7 4
3 0
4 0
6 4
3 1
7 4
5 1
5 0
3 1
1 4
4 1
1 3
6 3
2 4
4 0
2 0
6 3
3 0
1 3
5 3
7 4
0 5
2 5
5 1
3 5
8 5
4 1
5 1
5 0
1 3
5 7
3 0
8 5
0 2
4 6
0 6
0 3
4 0
8 5
5 1
1 4
5 0
3 1
5 7
3 0
10 7
0 2
9 2
5 8
3 9
...

output:

RBBRBRBBR
RBR
RBBRB
RBRBRR
RBRRBRRBR
RBR
RBRBBRB
RBRRRBR
RBRR
RBBRBR
RBRBRB
RBRBRBR
RBRRRBRB
RBR
RBBBBRBR
RBRRRBRB
RBR
RBBRBRBRRB
RBRRBRRR
RBRBRBRRRR
RBRBRBRBRR
RBBBRBBBRB
RBR
RBRBRBR
RBRRRR
RBBRBRBR
RBRR
RBBRBBB
RBRBRBBBBR
RBRBRBR
RBRBRBRR
RBRRRR
RBBRBR
RBR
RBR
RBRRRBRRR
RBRBBRB
RBRBR
RBRBRRBRRR
RB...

result:

wrong answer cycle detected (test case 22)