QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#554183#8544. Colorful Graph 2ucup-team1231#WA 0ms8728kbC++141.3kb2024-09-09 08:19:402024-09-09 08:19:41

Judging History

你现在查看的是最新测评结果

  • [2024-09-09 08:19:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8728kb
  • [2024-09-09 08:19:40]
  • 提交

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);
        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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8728kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

BBR
BBRR
BBBRBR

result:

wrong answer cycle detected (test case 3)