QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644867 | #8544. Colorful Graph 2 | Dukerki | ML | 1ms | 5708kb | C++20 | 2.5kb | 2024-10-16 15:43:50 | 2024-10-16 15:43:51 |
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;
}
}
continue;
}
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<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);
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5708kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRB RRRB RBBBRB
result:
ok ok (3 test cases)
Test #2:
score: -100
Memory Limit Exceeded
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 ...