QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644914 | #8544. Colorful Graph 2 | asaltfish | WA | 70ms | 5856kb | C++23 | 4.9kb | 2024-10-16 15:59:53 | 2024-10-16 15:59:55 |
Judging History
answer
//#include<cstdio>
//#include<iostream>
//#include<cmath>
//#include<algorithm>
//#include<string.h>
//#include<iomanip>
//#include<numeric>
//#include<stack>
//#include<deque>
//#include<queue>
//#include<vector>
//#include<map>
//#include<set>
//#define ll long long
//#define endl "\n"
//using namespace std;
//inline int read() { register int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-')w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9')s = s * 10 + ch - '0', ch = getchar(); return s * w; }
//ll t, n, m, l, r, ans[200005];
//vector<ll>e[200005];
//set<int>st;
//void dfs(ll x, bool flag)
//{
// ans[x] = flag;
// for (auto v : e[x])
// {
// if (ans[v] != -1) {
// if (ans[v] == flag) {
// if (st.count((v + 1) % n) != 0) {
// dfs((v + 1) % n, !flag);
// }
// else {
// ans[(v + 1) % n] = !flag;
// }
// if (st.count((v - 1 + n) % n) != 0) {
// dfs((v - 1 + n) % n, !flag);
// }
// else {
// ans[(v - 1 + n) % n] = !flag;
// }
// }
// }
// dfs(v, !flag);
// }
//}
//int main()
//{
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
// cin >> t;
// while (t--)
// {
// cin >> n >> m;
// fill(ans, ans + n, -1);
// if (!m)
// {
// ll now = 0;
// for (int i = 0; i < n; i++)
// {
// cout << (now ? 'R' : 'B');
// now = 1 - now;
// }
// cout << endl;
// continue;
// }
// vector<char>ans(n, '0');
// vector<pair<int, int>>vt;
// st.clear();
// for (int i = 1; i <= m; i++)
// {
// cin >> l >> r;
// st.insert(l);
// st.insert(r);
// e[l].push_back(r);
// e[r].push_back(l);
// }
// for (auto i : st)
// {
// if (ans[i] != -1)
// dfs(i, 0);
// } x 1 __int64
//
// char p;
// // int i = *(st.begin()), sum = 1;
// // for (;sum<=n; i=(i+1)%n)
// // {
// // sum++;
// // if (ans[i] == '0')
// // {
// // ans[i] = (p == 'R' ? 'B' : 'R');
// // }
// // p = ans[i];
// // }
// for (int i = 0; i < n; i++) {
// cout << (ans[i] == -1 ? 'R' : (ans[i] == 0 ? 'R' : 'B'));
// e[i].clear();
// }
//
// cout << endl;
//
// }
// return 0;
//}
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<iomanip>
#include<numeric>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define endl "\n"
using namespace std;
inline int read() { register int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-')w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9')s = s * 10 + ch - '0', ch = getchar(); return s * w; }
ll t, n, m, l, r, ans[200005];
vector<ll>e[200005];
set<int>st;
void bfs(ll x, bool flag)
{
deque<ll>q;
ans[x] = flag;
q.push_back(x);
while (q.size())
{
ll now = q.front();
q.pop_front();
for (auto i : e[now])
{
if (ans[i] == -1)
{
ans[i] = 1 - flag;
q.push_back(i);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> t;
while (t--)
{
cin >> n >> m;
fill(ans, ans + n, -1);
if (!m)
{
ll now = 0;
for (int i = 0; i < n; i++)
{
cout << (now ? 'R' : 'B');
now = 1 - now;
}
cout << endl;
continue;
}
st.clear();
for (int i = 1; i <= m; i++)
{
cin >> l >> r;
st.insert(l);
st.insert(r);
e[l].push_back(r);
e[r].push_back(l);
}
for (auto i : st)
{
if (ans[i] == -1)
{
bfs(i, 0);
}
}
char p;
int i = *(st.begin()), sum = 1;
for (; sum <= n; i = (i + 1) % n)
{
sum++;
if (ans[i] == -1)
{
ans[i] = 1 - p;
}
p = ans[i];
}
for (int i = 0; i < n; i++) {
cout << (ans[i] == 0 ? 'R' : 'B');
e[i].clear();
}
cout << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5856kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRB RRBB RBBRBR
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 70ms
memory: 3540kb
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:
RBBBBRBBR BRB RBBRB RRBRBB RRBBBRBRB BRB RBRBBRB RBRBBBR RRBB RBBRBR RBRBRB RBBBRBR RBRBBBRB BRB RBBBBRBR RBRBBBRB BRB RBBBBBBRBB RRBBBRBB RRBBBBRBBB RRBBBRBBBB RBBBBRBBRB BRB RRBRBRB RRBBBB RBBRBBBB RRBB RBBBRBB RRBBBRBBBB RRBBRBB RRBRBRBB RRBBBB RBBRBR BRB BRB RRBBBRBBB RBBRBRB RBRBR RRBBRBBRBB RB...
result:
wrong answer cycle detected (test case 1)