QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415606#8544. Colorful Graph 2defnotmeeWA 1ms3724kbC++201.9kb2024-05-21 04:48:362024-05-21 04:48:36

Judging History

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

  • [2024-05-21 04:48:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2024-05-21 04:48:36]
  • 提交

answer

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define O_O
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double dbl;
typedef long double dbll; 
const ll INFL = 4e18+25;
const int INF = 1e9+42;
const double EPS = 1e-7;
const int MOD = (1<<23)*17*7 + 1; // 998244353
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;

    while(t--){
        int n, m;
        cin >> n >> m;

        vector<bstring<int>> g(n);
        vector<int> deg(n);

        for(int i = 0; i < n; i++){
            g[i].push_back((i+1)%n);
            g[(i+1)%n].push_back(i);
            deg[i] = 2;
        }

        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
            deg[a]++, deg[b]++;
        }

        vector<int> q;
        for(int i = 0; i< n; i++)
            if(deg[i] == 2)
                q.push_back(i);
        
        vector<int> color(n);
        while(!q.empty()){
            int cur = q.back();
            q.pop_back();

            color[cur] = 1;
            for(int i : g[cur]){
                if(color[i] == 1)
                    color[cur] = -1;
                deg[i]--;
                if(deg[i] == 2)
                    q.push_back(i);
            }
        }

        for(int i = 0; i < n; i++){
            if(color[i] == 1)
                cout << "R";
            else cout << "B";
        }
        cout << '\n';
    }
    
    return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3724kb

input:

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

output:

BBR
RBRB
BRBRBR

result:

wrong answer cycle detected (test case 3)