QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474212 | #8544. Colorful Graph 2 | real_sigma_team# | WA | 205ms | 3564kb | C++20 | 1.2kb | 2024-07-12 16:41:29 | 2024-07-12 16:41:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
void solve();
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
g[x].push_back(x);
g[y].push_back(x);
}
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n;
g[i].push_back(j);
g[j].push_back(i);
}
vector<int> deg(n);
for (int i = 0; i < n; ++i) deg[i] = g[i].size();
set<pair<int, int>> st;
for (int i = 0; i < n; ++i) {
st.emplace(deg[i], i);
}
vector<bool> used(n);
string ans(n, '#');
auto go = [&](auto go) -> void {
if (st.empty()) return;
int u = st.begin()->second;
st.erase(st.begin());
used[u] = true;
vector<int> vert;
for (auto to : g[u]) {
if (!used[to]) {
st.erase({deg[to], to});
vert.push_back(to), deg[to]--;
st.emplace(deg[to], to);
}
}
go(go);
if (vert.size() == 0) {
ans[u] = 'R';
} else {
ans[u] = 'B' + 'R' - ans[vert[0]];
}
};
go(go);
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RBR BRBR BRRBRB
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 205ms
memory: 3512kb
input:
100000 9 6 2 0 4 6 3 6 0 6 0 7 2 6 3 0 5 2 2 4 2 0 6 3 1 5 4 1 2 4 9 6 3 1 6 4 8 1 3 6 1 6 8 6 3 0 7 4 3 0 4 0 6 4 3 1 7 4 5 1 5 0 3 1 1 4 4 1 1 3 6 3 2 4 4 0 2 0 6 3 3 0 1 3 5 3 7 4 0 5 2 5 5 1 3 5 8 5 4 1 5 1 5 0 1 3 5 7 3 0 8 5 0 2 4 6 0 6 0 3 4 0 8 5 5 1 1 4 5 0 3 1 5 7 3 0 10 7 0 2 9 2 5 8 3 9 ...
output:
RBRBRBRBR RBR BRRBR BRBRBR BRBRBRRBR RBR RRBBRBB BRBRBRB BRBR BRRBRB BRBRBR RBRBRRB BRBBBRBB RBR RBBBRBRB BRBRBRBB RBR BRBRBRRBBR RBRRBRRB RBBRRRBBBR BRBRRBBBRB RBBRBRRRBB RBR RBRBRBR BRBRBR BRRBRBBR BRBR BRBRBBR BRRBBRRBRB RBRBRBR BRRBBRRB BRBBRB RBRBBB RBR RBR BRBBRBBBR BBRBRBR RBRRB RBRBRRBRBR BR...
result:
wrong answer cycle detected (test case 1)