QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576624 | #8544. Colorful Graph 2 | ucup-team4435# | RE | 0ms | 3648kb | C++20 | 2.7kb | 2024-09-19 21:19:36 | 2024-09-19 21:19:36 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector <pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const ll INF = 2e18;
const int INFi = 1e9;
const int N = 2e5 + 5;
const int LG = 20;
void solve() {
int n, m; cin >> n >> m;
vector<vi> g(n);
vi tp(n, -1);
rep(i, n - 1) g[i].push_back(i + 1);
rep(_, m) {
int u, v; cin >> u >> v;
if (u > v) swap(u, v);
g[u].emplace_back(v);
}
function<void(int, int)> dfs = [&] (int l, int r) {
assert(tp[l] != -1 && tp[r] != -1);
if (l + 1 == r) return;
int v = l;
bool ok = false;
while (v != r) {
assert(!g[v].empty() && v >= l && v < r);
int u = g[v].back();
g[v].pop_back();
if (u != r) {
assert(tp[u] == -1);
tp[u] = tp[v] ^ 1;
ok = true;
}
dfs(v, u);
v = u;
}
assert(ok);
};
tp[0] = 0, tp[n - 1] = 1;
dfs(0, n - 1);
rep(i, n) if (tp[i] == -1) tp[i] = 0;
rep(i, n) cout << "RB"[tp[i]];
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
cin >> t;
rep(i, t) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
RBB RBRB RBBRBB
result:
ok ok (3 test cases)
Test #2:
score: -100
Runtime Error
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 ...