QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#609005 | #8544. Colorful Graph 2 | lottle1212 | RE | 0ms | 22416kb | C++14 | 2.0kb | 2024-10-04 10:11:43 | 2024-10-04 10:11:45 |
Judging History
answer
#include <iostream>
#include <bitset>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define ll long long
#define db double
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define mp make_pair
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vl vector <ll>
#define eb emplace_back
#define pb push_back
#define sz(x) ((int) x.size())
#define ms(f, x) memset(f, x, sizeof (f))
#define ACN(i, h_u) for (int i=h_u; i; i=e[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
res=0; bool f=false; char ch=getchar();
while (ch<'0'||ch>'9') f|=(ch=='-'), ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
res=(f?-res:res);
}
template <typename INT, typename ...Args>
void rd(INT &res, Args &..._res) { rd(res), rd(_res...); }
//dfs
const int maxn=2e5;
const int N=maxn+10;
set <int> e[N], s[N]; bool col[N]; int n, m, stk[N];
//wmr
//incra
//lottle
signed main() {
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("8544.in", "r", stdin);
// freopen("8544.out", "w", stdout);
int T; rd(T);
while (T--) {
rd(n, m);
L(i, 0, n) set <int> ().swap(e[i]), set <int> ().swap(s[i]);
L(i, 2, n) e[i].insert(i-1), e[i].insert(i+1);
e[1].insert(n), e[1].insert(2); e[n].insert(n-1), e[n].insert(1);
while (m--) { int u, v; rd(u, v); e[u+1].insert(v+1); e[v+1].insert(u+1); }
L(i, 1, n) s[sz(e[i])].insert(i); int top=0;
while (true) {
int sign=!s[2].empty()?2:!s[1].empty()?1:0;
if (sign) {
int u=*s[sign].begin(); s[sign].erase(u); stk[++top]=u;
for (int v: e[u]) s[sz(e[v])].erase(v), e[v].erase(u), s[sz(e[v])].insert(v);
} else break;
}
while (top) col[stk[top]]=!col[*e[stk[top]].begin()], --top;
L(i, 1, n) putchar(col[i]?'R':'B');
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22416kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RBR RBRB RBBRBR
result:
ok ok (3 test cases)
Test #2:
score: -100
Runtime Error
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 ...