Task: | Graph painting |
Sender: | asdf |
Submission time: | 2024-09-28 14:07:01 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.01 s | details |
#3 | ACCEPTED | 0.12 s | details |
Code
#include <bits/stdc++.h> using namespace std; #define int long long string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif const int N = 1e5 + 5; const int M = 2e5 + 5; int n, m; vector<int> adj[N]; int deg[N]; int col[N]; void dfs(int u, int c) { col[u] = c; for (int v : adj[u]) { if (col[v] == -1) { dfs(v, 1 - c); } } } void solve() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; deg[u]++; deg[v]++; adj[u].push_back(v); adj[v].push_back(u); } vector<int> order(n); for (int i = 1; i <= n; i++) { order[i - 1] = i; } sort(order.begin(), order.end(), [&](int i, int j){ return deg[i] > deg[j]; }); for (int u : order) { if (col[u] == -1) { dfs(u, 1); } } for (int i = 1; i <= n; i++) { cout << (col[i] ? "R" : "B") << ' '; } cout << '\n'; } void clean() { for (int i = 1; i <= n; i++) { adj[i].clear(); col[i] = -1; deg[i] = 0; } } signed main() { cin.tie(0)->sync_with_stdio(0); memset(col, -1, sizeof col); memset(deg, 0, sizeof deg); int t; cin >> t; while (t--) { solve(); clean(); } }
Test details
Test 1
Verdict: ACCEPTED
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 R R B B R R B B R B B B B B R R R B R B R B B R R B B B B R R R B ... Truncated |
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 B R R R R R R R R B R R R ... Truncated |
Test 3
Verdict: ACCEPTED
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 |
---|
R R R B B R R B B R R B R R R ... Truncated |