QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645112#8544. Colorful Graph 2aurorawhiteseaWA 88ms3992kbC++201.4kb2024-10-16 16:56:172024-10-16 16:56:18

Judging History

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

  • [2024-10-16 16:56:18]
  • 评测
  • 测评结果:WA
  • 用时:88ms
  • 内存:3992kb
  • [2024-10-16 16:56:17]
  • 提交

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)