QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#554184 | #8544. Colorful Graph 2 | ucup-team1231# | WA | 69ms | 9052kb | C++14 | 1.3kb | 2024-09-09 08:20:29 | 2024-09-09 08:20:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m, deg[200005];
bool vis[200005];
vector<int> G[200005];
void adde(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
char S[200005];
void solve() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 0; i < n; i++) adde(i % n + 1, (i + 1) % n + 1);
for(int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v); u++; v++;
G[u].push_back(v);
G[v].push_back(u);
}
queue<int> que;
for(int i = 1; i <= n; i++) if((deg[i] = G[i].size()) <= 2) {
que.push(i); vis[i] = true;
} else vis[i] = false;
vector<int> seq;
while(!que.empty()) {
int v = que.front(); que.pop();
seq.push_back(v);
for(auto u : G[v]) if(!vis[u]) {
deg[u]--;
if(deg[u] <= 2) {
vis[u] = true; que.push(u);
}
}
}
reverse(seq.begin(), seq.end());
for(int i = 1; i <= n; i++) S[i] = ' ';
for(auto v : seq) {
for(auto u : G[v]) if(S[u] != ' ') S[v] = S[u] == 'R' ? 'B' : 'R';
if(S[v] == ' ') S[v] = 'R';
}
printf("%s\n", S + 1);
}
int main() {
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9052kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BBR BBBR RBRRBB
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 69ms
memory: 8848kb
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:
BRBBBBRRR BBRBBBRRR RRBBRBRRR RRRRBBRRR RBRBBBRRB BBRBBBRRB BBBRRRBRB BBBRRRRRB BBBRRRRRB RRBRBBRRB BBBRRBRRB BBBBBRRRB RRRBBBBRB BBRBBBBRB RRBBBRBBB RRRBBBBRB BBRBBBBRB RRBBBBBBRR RRRBBBRBRR RRRRRRRBBB RRRRRRBBBB RRBBBBRRBR BBRBBBRRBR RBBBRRBRBR RRRBBBBRBR BBRRBBBBBR BBBRBBBBBR BBRRRBBBBR RRRRRRBBB...
result:
wrong answer the length doesn't equal n (test case 2)