QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#388252#8544. Colorful Graph 2ucup-team1516#WA 49ms3596kbC++203.7kb2024-04-13 14:13:582024-04-13 14:13:59

Judging History

你现在查看的是最新测评结果

  • [2024-04-13 14:13:59]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:3596kb
  • [2024-04-13 14:13:58]
  • 提交

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)