QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662433#8544. Colorful Graph 2HHY_zZhu#WA 113ms3604kbC++171.9kb2024-10-21 00:10:252024-10-21 00:10:28

Judging History

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

  • [2024-10-21 00:10:28]
  • 评测
  • 测评结果:WA
  • 用时:113ms
  • 内存:3604kb
  • [2024-10-21 00:10:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;

//const int MN = 2e5 + 20;
const int INF = 2e9 + 1000;
const LL INFLL = 8e18 + 1000;
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
//模板区域~~~~~~~

//模板结束~~~~~~~

void solve() {
    int n, m; cin >> n >> m;
    V<V<int>> e(n);
    auto MOD = [&](int x) {
        while(x >= n) x -= n;
        while(x < 0) x += n;
        return x;
    };
    auto st = [&](int & x, int & y) {
        if(MOD(y - x) < MOD(x - y)) swap(x, y); 
    };
    V<pi> E(m + 1);
    for(int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        st(x, y);
        E[i] = {x, y};
    }
    sort(all1(E), [&](pi a, pi b) {
        return MOD(a.se - a.fi) < MOD(b.se - b.fi);
    });
    V<int> nxt(n);
    for(int i = 0; i < n; i++) nxt[i] = MOD(i + 1);
    for(int i = 1; i <= m; i++) {
        auto [x, y] = E[i];
        nxt[x] = y;
    }
    for(int i = 0; i < n; i++) {
        e[i].pb(nxt[i]);
        e[nxt[i]].pb(i);
    }

    V<int> c(n), vis(n);
    auto dfs = [&](int x, auto dfs) -> void {
        vis[x] = 1;
        for(auto y : e[x]) {
            if(vis[y]) ;
            else {
                c[y] = c[x] ^ 1;
                dfs(y, dfs);
            }
        }
    };
    for(int i = 0; i < n; i++) {
        if(!vis[i]) dfs(i, dfs);
    }
    for(int i = 0; i < n; i++) cout << (c[i] ? 'R' : 'B');
    cout << endl;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) 
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

BRB
BRRB
BRBBRR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 113ms
memory: 3588kb

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:

BBRBRBRRB
BRB
BRBBR
BRBRBB
BRRBRBRRB
BRB
BBRBRBR
BBBRRRB
BRRB
BRBBRR
BRBRRB
BBBRBRR
BBRBRRRB
BRB
BBRRBBRR
BBRBRRRB
BRB
BRBBBRBRBR
BRRBBRBB
BRRRBRBRBB
BRBBRBRRRB
BRBRBRBRRB
BRB
BRRBRRB
BRRBRB
BRBBRRRR
BRRB
BRBBRBR
BRRBRBRBRB
BRRBRBB
BRBRBBRB
BRRBBB
BRBBRR
BRB
BRB
BRRBBBRRB
BBRBRRB
BRBRR
BRBRBRRBRB
BR...

result:

wrong answer cycle detected (test case 7)