QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554184#8544. Colorful Graph 2ucup-team1231#WA 69ms9052kbC++141.3kb2024-09-09 08:20:292024-09-09 08:20:30

Judging History

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

  • [2024-09-09 08:20:30]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:9052kb
  • [2024-09-09 08:20:29]
  • 提交

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)