| Task: | Graph painting |
| Sender: | \(._.)/ |
| Submission time: | 2024-09-28 14:53:44 +0300 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | RUNTIME ERROR |
| test | verdict | time | |
|---|---|---|---|
| #1 | RUNTIME ERROR | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | RUNTIME ERROR | 0.20 s | details |
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: RUNTIME ERROR
| 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: RUNTIME ERROR
| 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) |
