QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644875#8544. Colorful Graph 2DukerkiWA 59ms5732kbC++202.3kb2024-10-16 15:45:352024-10-16 15:45:35

Judging History

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

  • [2024-10-16 15:45:35]
  • 评测
  • 测评结果:WA
  • 用时:59ms
  • 内存:5732kb
  • [2024-10-16 15:45:35]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<iomanip>
#include<numeric>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll               long long
#define endl             "\n"
using namespace std;
inline int read() { register int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-')w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9')s = s * 10 + ch - '0', ch = getchar(); return s * w; }
ll t, n, m, l, r, ans[200005];
vector<ll>e[200005];
set<int>st;
void dfs(ll x, bool flag)
{
    ans[x] = flag;
    for (auto v : e[x])
    {
        if (ans[v] != -1) {
            if (ans[v] == flag) {
                if (st.count((v + 1) % n) != 0 && ans[(v + 1) % n] == -1) {
                    dfs((v + 1) % n, !flag);
                }
                else {
                    ans[(v + 1) % n] = !flag;
                }
                if (st.count((v - 1 + n) % n) != 0 && ans[(v - 1 + n) % n] == -1) {
                    dfs((v - 1 + n) % n, !flag);
                }
                else {
                    ans[(v - 1 + n) % n] = !flag;
                }
            }
            continue;
        }
        dfs(v, !flag);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        fill(ans, ans + n, -1);
        if (!m)
        {
            ll now = 0;
            for (int i = 0; i < n; i++)
            {
                cout << (now ? 'R' : 'B');
                now = 1 - now;
            }
            cout << endl;
            continue;
        }
        vector<pair<int, int>>vt;
        st.clear();
        for (int i = 1; i <= m; i++)
        {
            cin >> l >> r;
            st.insert(l);
            st.insert(r);
            e[l].push_back(r);
            e[r].push_back(l);
        }
        for (auto i : st)
        {
            if (ans[i] == -1)
                dfs(i, 0);
        }
        char p;
        for (int i = 0; i < n; i++) {
            cout << (ans[i] == -1 ? 'R' : (ans[i] == 0 ? 'R' : 'B'));
            e[i].clear();
        }

        cout << endl;

    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5732kb

input:

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

output:

BRB
RRRB
RBBBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 59ms
memory: 5704kb

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:

RBBBBBRBB
BRB
RRBRR
RRRRBB
BRBBBBRBB
BRB
RRRBBRR
RRRBBBR
RRRB
RBRBBB
RRRBRR
RRRRRBR
RRRBBBRR
BRB
RBBBRBBB
RRRBBBRR
BRB
RRBBBBBRRR
BRBRBRBB
RRRRRRRBBB
RRRRRRBBBB
RRRBRRRBRR
BRB
BRBBRBB
RRRBBB
RRBRRRRR
RRRB
RRBBRRR
RRRRRRBBBB
RRRRRBB
BRBBRBBB
RRRBBB
RBBBRB
BRB
BRB
BRBBBRBRB
RRRRBRR
RRRBR
BRBRRBBRBR
RR...

result:

wrong answer cycle detected (test case 22)