QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#608949 | #8544. Colorful Graph 2 | lottle1212 | ML | 3ms | 22364kb | C++14 | 1.9kb | 2024-10-04 09:35:07 | 2024-10-04 09:35:24 |
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;
//wmr
//incra
void dfs() {
int sign=!s[2].empty()?2:!s[1].empty()?1:0;
if (sign) {
int u=*s[sign].begin(); s[sign].erase(u);
for (int v: e[u]) s[sz(e[v])].erase(v), e[v].erase(u), s[sz(e[v])].insert(v);
dfs(); col[u]=!col[*e[u].begin()];
}
}
//lottle
signed main() {
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".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);
dfs();
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: 3ms
memory: 22364kb
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
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 ...