QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645112 | #8544. Colorful Graph 2 | aurorawhitesea | WA | 88ms | 3992kb | C++20 | 1.4kb | 2024-10-16 16:56:17 | 2024-10-16 16:56:18 |
Judging History
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].push_back(v);
edge[v].push_back(u);
}
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: 3624kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RBR RBBR RBRRBR
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 88ms
memory: 3992kb
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:
RBRBRRBRB RBR RBRRB RBRBBR RBBRBBRBR RBR RBBRBBR RBBBBRB RBBR RBRRBR RBBRBR RBRBBRB RBBBBRBR RBR RBRBRRBR RBBBBRBR RBR RBRBRBRRRB RBBRBBBR RBRBRBBBBR RBRBRBRBBR RBRBRRBRBR RBR RBRBRBR RBBBBR RBRRRRRB RBBR RBRBBRB RBRBRRRRBR RBRBRBR RBRBRBBR RBBBBR RBRRBR RBR RBR RBBBRBBBR RBRBRBR RBBRB RBRBBRBBBR RB...
result:
wrong answer cycle detected (test case 8)