QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644997#8544. Colorful Graph 2CreditWA 49ms9968kbC++172.4kb2024-10-16 16:23:462024-10-16 16:23:48

Judging History

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

  • [2024-10-16 16:23:48]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:9968kb
  • [2024-10-16 16:23:46]
  • 提交

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]) {
            // cout << e[i].first << " " << e[i].second << endl;
            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;
                }
            }
            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: 9968kb

input:

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

output:

RBB
RRBB
RBBRRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 49ms
memory: 9656kb

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:

RBBBBRRBB
RBB
RRBBR
RRRBBB
RRBBBBRBB
RBB
RRRBBBR
RRRBBBB
RRBB
RBRBBR
RRRBBR
RRRRRBB
RRRBBBBR
RBB
RBBBRBBR
RRRBBBBR
RBB
RRBBBBBBRR
RRBRRBBB
RRRRRRBBBB
RRRRRBBBBB
RRBBRBBBRR
RBB
RRBBRBB
RRBBBB
RRBBRRRR
RRBB
RRBBBRR
RRRRRBBBBB
RRRRBBB
RRBBRBBB
RRBBBB
RBBRRB
RBB
RBB
RRBBBBRRB
RRRRBBR
RRRBB
BRRRBBBRRR
RR...

result:

wrong answer cycle detected (test case 47)