QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#646392 | #8544. Colorful Graph 2 | Iron_gainer | WA | 80ms | 3616kb | C++20 | 1.4kb | 2024-10-16 22:40:54 | 2024-10-16 22:40:56 |
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+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)