QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645030#8544. Colorful Graph 2CreditWA 53ms10100kbC++172.9kb2024-10-16 16:35:522024-10-16 16:35:53

Judging History

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

  • [2024-10-16 16:35:53]
  • 评测
  • 测评结果:WA
  • 用时:53ms
  • 内存:10100kb
  • [2024-10-16 16:35:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 3e5 + 5;
const int mod = 1e9 + 5;
int n, m;

vector<pair<ll, ll>> e;
vector<ll> v[200005];
ll co[200005];
bool vis[1000005];
void dfs(ll x, ll color, ll fa) {
    vis[x] = 1;
    if (co[x] == -1 && v[x].size() >=1) {
        co[x] = 1;
    }
    for (auto i : v[x]) {
        if (vis[i]) {
            continue;
        }
        if (i == fa)continue;
        if (co[i] == -1)
        {
            co[i] = co[x] ^ 1;
        }
        dfs(i, co[i], x);
    }
}
void solve()
{
    cin >> n >> m;
    e.clear();
    for (int i = 0;i < n;i++) {
        v[i].clear();
        co[i] = -1;
        vis[i] = 0;
    }
    for (int i = 1;i <= m;i++) {
        ll x, y;cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        e.push_back(make_pair(x, y));
    }
    for (int i = 0;i < n;i++) {
        // if (co[i] == -1) co[i] = 1;
        dfs(i, 1, -1);
    }
    bool flag = 0;
    for (int i = 0;i < e.size();i++) {
        if (co[e[i].first] == co[e[i].second]) {
            bool fg1 = 0,fg2 = 0;
            for (int j = e[i].first + 1;j != e[i].second;j++) {
                if (j >= n)j %= n;
                if (co[j] == (co[e[i].first] ^ 1)) {
                    fg1 = 1;
                    break;
                }
            }
            for (int j = e[i].second + 1;j != e[i].first;j++) {
                if (j >= n)j %= n;
                if (co[j] == (co[e[i].first] ^ 1)) {
                    fg2 = 1;
                    break;
                }
            }
            if(fg1 == 0)
            for (int j = e[i].first + 1;j != e[i].second;j++) {
                if (j >= n)j %= n;
                // cout << j << endl;
                if (co[j] == (co[e[i].first] ^ 1))break;
                if (co[j] == -1) {
                    co[j] = co[e[i].first] ^ 1;
                    break;
                }
            }
            if(fg2 == 0)
            for (int j = e[i].second + 1;j != e[i].first;j++) {
                if (j >= n)j %= n;
                if (co[j] == (co[e[i].first] ^ 1))break;
                if (co[j] == -1) {
                    co[j] = co[e[i].first] ^ 1;
                    break;;
                }
            }
        }
    }
    // for (int i = 0;i < n;i++)cout << co[i] <<" ";
    for (int i = 0;i < n;i++) {
        if (co[i] == -1) {
            if (flag == 0) {
                cout << "R";
                flag = 1;
            }
            else {
                cout << "B";
            }
        }
        else if (co[i] == 1) {
            cout << "R";
        }
        else {
            cout << "B";
        }
    }
    cout << "\n";
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9920kb

input:

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

output:

RBB
RRBB
RRBBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 53ms
memory: 10100kb

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:

RRBBBBRBB
RBB
RRBBR
RRRBBB
RRBBBBRBB
RBB
RRRBBBR
RRRBBBB
RRBB
RBRRBB
RRRBBR
RRRRRBB
RRRBBBBR
RBB
RRBBRBBB
RRRBBBBR
RBB
RRBBBBBBRR
RRBRRBBB
RRRRRRBBBB
RRRRRBBBBB
RRBBRBBBBR
RBB
RRBBRBB
RRBBBB
RRBBRRRR
RRBB
RRBBBRR
RRRRRBBBBB
RRRRBBB
RRBBRBBB
RRBBBB
RRBBRB
RBB
RBB
RRBBBBRRB
RRRRBBR
RRRBB
BRRRRBBBRR
RR...

result:

wrong answer cycle detected (test case 47)