QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609067 | #8544. Colorful Graph 2 | lottle1212 | RE | 2ms | 22716kb | C++14 | 2.0kb | 2024-10-04 10:29:39 | 2024-10-04 10:29:39 |
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;
if (T<=5) 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;
}
if (T<=5) while (top) col[stk[top]]=!col[*e[stk[top]].begin()], --top;
L(i, 1, n) putchar(col[i]?'R':'B');
puts("");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 22716kb
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 ...
output:
BBBBBBBBB BBB BBBBB BBBBBB BBBBBBBBB BBB BBBBBBB BBBBBBB BBBB BBBBBB BBBBBB BBBBBBB BBBBBBBB BBB BBBBBBBB BBBBBBBB BBB BBBBBBBBBB BBBBBBBB BBBBBBBBBB BBBBBBBBBB BBBBBBBBBB BBB BBBBBBB BBBBBB BBBBBBBB BBBB BBBBBBB BBBBBBBBBB BBBBBBB BBBBBBBB BBBBBB BBBBBB BBB BBB BBBBBBBBB BBBBBBB BBBBB BBBBBBBBBB BB...