QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#630715#8544. Colorful Graph 2shiqiaqiaya#WA 74ms3624kbC++172.5kb2024-10-11 20:07:512024-10-11 20:07:53

Judging History

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

  • [2024-10-11 20:07:53]
  • 评测
  • 测评结果:WA
  • 用时:74ms
  • 内存:3624kb
  • [2024-10-11 20:07:51]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
using i128 = __int128;
using f64 = double;
using f128 = long double;
constexpr i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
ostream & operator << (ostream & os, i128 t) {
    if (t == 0) os << 0;
    if (t < 0) t = -t, os << '-';
    string s;
    for (; t; s += '0' + t % 10, t /= 10);
    return reverse(s.begin(), s.end()), os << s;
}
template <class T, class ... A> void debug(T t, A ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }

void QAQ() {
    int n, m;
    cin >> n >> m;

    vector adj(n + 1, vector<int>());

    int tm = 0;

    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        u++, v++;
        if (abs(u - v) != 1) {
            adj[u].emplace_back(v), adj[v].emplace_back(u);
            tm++;
        }
    }

    vector<char> ans(n + 1, ' ');

    for (int i = 1; i <= n; i++) {
        if (ans[i] == ' ') {
            auto dfs = [&](auto && self, int u) -> void {
                set<char> t;
                for (auto & v : adj[u]) {
                    if (ans[v] != ' ') {
                        t.insert(ans[v]);
                    }
                }
                if (t.size() == 0) {
                    ans[u] = 'B';
                } else if (t.size() == 1) {
                    if (*t.begin() == 'B') {
                        ans[u] = 'R';
                    } else {
                        ans[u] = 'B';
                    }
                } else {
                    ans[u] = 'R';
                }
                for (auto & v : adj[u]) {
                    if (ans[v] == ' ') {
                        self(self, v);
                    }
                }
            };

            dfs(dfs, i);
        }
    }

    if (tm == 0) {
        ans[1] = 'R';
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i];
    }
    cout << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

RBB
BBBR
BBRBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 74ms
memory: 3620kb

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:

BBRBBBRRB
RBB
BBRBB
BBBBRR
BBBRBBRBR
RBB
BBBRRBB
BBBRRRB
BBBR
BBRBRB
BBBRBB
BBBBBRB
BBBRRRBB
RBB
BBRRRBRB
BBBRRRBB
RBB
BBRRRRRBBB
BBBRBBRR
BBBBBBBRRR
BBBBBBRRRR
BBRRBBRRBB
RBB
BBBBRBR
BBBRRR
BBRBBBBB
BBBR
BBRRBBB
BBBBBBRRRR
BBBBBRR
BBBBRBRR
BBBRRR
BBRBRB
RBB
RBB
BBBRRBBRR
BBBBRBB
BBBRB
BBBBBRBBRR
BB...

result:

wrong answer cycle detected (test case 374)