QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393012#8544. Colorful Graph 2ucup-team2894RE 0ms0kbC++171.9kb2024-04-18 03:03:382024-04-18 03:03:39

Judging History

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

  • [2024-04-18 03:03:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-18 03:03:38]
  • 提交

answer

#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()

using namespace std;

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

void solve() {
    int T;
    cin >> T;
    while(T--) {
        int N, M;
        cin >> N >> M;
        vector<set<int>> graph(N + 5);
        for (int i = 0; i < N; i++) {
            graph[i].insert((i + 1)%N);
            graph[(i + 1)%N].insert(i);
        }
        for (int i = 1; i <= M; i++) {
            int a, b;
            cin >> a >> b;
            graph[a].insert(b);
            graph[b].insert(a);
        }
        set<int> st;
        vector<int> stk;
        for (int n = 0; n < N; n++) {
            st.insert(n);
            if (graph[n].size() == 2 && stk.size() < N - 2) {
                stk.push_back(n);
            }
        }
        int idx = 0;
        while(st.size() > 2) {
            int n = stk[idx++];
            st.erase(n);
            for (int e : graph[n]) {
                graph[e].erase(n);
                if (graph[e].size() == 2) {
                    stk.push_back(e);
                }
            }
        }
        vector<int> clr(N + 5);
        while(stk.size()) {
            int n = stk.back();
            stk.pop_back();
            // cout << n << " " << graph[n].size() << endl;
            // cout << graph[n].size() << endl;
            assert(graph[n].size() == 2);
            if (!clr[*graph[n].begin()] && !clr[*next(graph[n].begin())]) {
                clr[n] = 1;
            }
        }
        for (int i = 0; i < N; i++) {
            cout << "BR"[clr[i]]; 
        }
        cout << "\n";
    }
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    // freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    solve();
    cerr << "\n\nConsumed " << TIME << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

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

output:


result: