QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644992#8544. Colorful Graph 2CreditWA 57ms9752kbC++172.4kb2024-10-16 16:21:362024-10-16 16:21:37

Judging History

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

  • [2024-10-16 16:21:37]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:9752kb
  • [2024-10-16 16:21:36]
  • 提交

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: 2ms
memory: 9752kb

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: 57ms
memory: 9196kb

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
RRBBRRBBRR
RBB
RRBBRBB
RRBBBB
RRBBRRRR
RRBB
RRBBBRR
RRRRRBBBBB
RRRRBBB
RRBBRBBB
RRBBBB
RBBRRB
RBB
RBB
BRBBBRRRB
RRRRBBR
RRRBB
BRRRBBBRRR
RR...

result:

wrong answer cycle detected (test case 47)