QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388252 | #8544. Colorful Graph 2 | ucup-team1516# | WA | 49ms | 3596kb | C++20 | 3.7kb | 2024-04-13 14:13:58 | 2024-04-13 14:13:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
if(x > y) {
x = y;
return true;
} else return false;
}
template<class T> bool chmax(T& x, T y){
if(x < y) {
x = y;
return true;
} else return false;
}
// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )
#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )
#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)
// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)
// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)
// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)
// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)
// for_earh
#define fore(e, v) for (auto&& e : v)
// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
template<class T, T(* op)(T, T), T(* e)()>
struct segment_tree{
int N;
vector<T> node;
segment_tree(int n) {
N = 1;
while(N < n) N *= 2;
node.resize(N * 2 - 1, e());
}
void update(int i, T x){
i += N - 1;
node[i] = x;
while(i > 0){
i = (i - 1) / 2;
node[i] = op(node[i * 2 + 1], node[i * 2 + 2]);
}
}
T get_val(int a, int b, int k = 0, int l = 0, int r = -1){
if(r == -1) r = N;
if(b <= l || r <= a) return e();
if(a <= l && r <= b) return node[k];
T vl = get_val(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = get_val(a, b, k * 2 + 2, (l + r) / 2, r);
return op(vl, vr);
}
};
int op(int a, int b) {
return a + b;
}
int e() {
return 0;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> u(m), v(m);
segment_tree<int, op, e> st(n);
rep (i, m) {
cin >> u[i] >> v[i];
st.update(u[i], 1);
st.update(v[i], 1);
if (u[i] > v[i]) swap(u[i], v[i]);
}
string S(n, 'R');
rep (i, m) {
if (st.get_val(u[i] + 1, v[i]) == 0) {
S[u[i] + 1] = 'B';
} else {
S[(u[i] - 1 + n) % n] = 'B';
}
}
if (m != 0) S[u[0]] = 'B';
else S[0] = 'B';
cout << S << '\n';
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRR RBBR BBRBRB
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 49ms
memory: 3596kb
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:
BBBRRBRRB BRR RBBBR BBRBRR BBBRRBRBR BRR BRBRRBB BBBRRRB RBBR RBBBRB BRBRBB BBRRBRB BBBRRRBB BRR BBRRRBRB BBBRRRBB BRR BBBBBRRBRR BBBRRBRR BBBBBRBRRR BBBRRBRRRR BBBBRBRRBB BRR BBRBRBR BBBRRR RBBBRRRR RBBR RBBRBRR BBBRRBRRRR BBBRBRR BBRBRBRR BBBRRR BBRBRB BRR BRR BBBBRBRRR BRBBRBB BRBRB BBBRBBRBRR RB...
result:
wrong answer cycle detected (test case 1)