CSES - Practice Contest 2024 - Results
Submission details
Task:Graph painting
Sender:\(._.)/
Submission time:2024-09-28 14:53:44 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#2ACCEPTED0.00 sdetails
#30.20 sdetails

Code

#include <algorithm>
#include <climits>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int algo(
    vector<pair<int, int>> &vertices,
    vector<vector<pair<int, int>>> &edges,
    vector<int> &colors,
    int m
) {
    int e = 0, i = 1;
    int limit = 0;
    if (m == 1) limit = 1;
    else limit = m / 2;
    while (e < limit) {
        int vert = vertices[i].second;
        // cout << "vert: " << vert << "\n";
        int vert_color = colors[vert];
        if (colors[vert] == -1) {
            vert_color = 0;
            colors[vert] = 0;
        }        // int vert_color = colors[vert] < 0 ? 0 : 1;
        for (auto u : edges[vert]) {
            if (colors[u.second] >= 0) {
                continue;
            }
            else {
                colors[u.second] = 1 - vert_color;
                e++;
            }
        }
        i++;
    }
    return 0;
}

int main(int argc, char *argv[])
{
	// Read the input parameters
	int t;
	cin >> t;

    for (int i = 0; i < t; i++) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> vertices(n + 1, make_pair(0, 0));
        vertices[0].first = INT_MAX;
        vector<vector<pair<int, int>>> edges(n + 1, vector<pair<int, int>>(0));
        vector<int> colors(n + 1, -1);
        // cout << "loop\n\n";
        for (int j = 0; j < m; j++) {
            int v1, v2;
            cin >> v1 >> v2;
            vertices[v1].first++;
            vertices[v2].first++;
            edges[v1].push_back({v1, v2});
            edges[v2].push_back({v2, v1});
        }
        for (int j = 1; j < n + 1; j++) {
            vertices[j].second = j;
        }
        sort(vertices.rbegin(), vertices.rend());
        // for (int a = 1; a < n + 1; a++) {
        //     cout << vertices[a].first << " " << vertices[a].second << "\n";
        // }
        // cout << "m: " << m << "\n";
        // for (int a = 0; a < m; a++) {
        //     for (auto u : edges[a]) {
        //         cout << u.first << " " << u.second << "\n";
        //     }
        // }
        algo(vertices, edges, colors, m);
        // cout << "colors:\n";
        // for (int a = 1; a < n + 1; a++) {
        //     cout << colors[a] << "\n";
        // }

        for (int j = 1; j < n + 1; j++) {
            char color = colors[j] == 0 ? 'B' : 'R';
            if (colors[j] == -1) color = 'R';
            cout << color << " ";
        }
        // cout << "\n\n";
        cout << "\n";
    }
	return 0;
}

Test details

Test 1

Verdict:

input
100
7 1
2 5
8 28
2 7
...

correct output
B R B B B B R 
R B B R B R B B 
R R B B B B R R R B 
B B R B R B 
B B B R B R R B R 
...

user output
R R R R B R R 

Test 2

Verdict: ACCEPTED

input
10
38 36
18 28
20 37
22 38
...

correct output
R R B R B R R R R R B B R B R ...

user output
R R R R R R R R R R R R R R R ...
Truncated

Test 3

Verdict:

input
1
100000 200000
89300 98492
33853 56822
92967 99427
...

correct output
R R R R B R R R B B B R B B B ...

user output
(empty)