QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644887#8544. Colorful Graph 2asaltfishWA 62ms5680kbC++234.9kb2024-10-16 15:50:022024-10-16 15:50:03

Judging History

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

  • [2024-10-16 15:50:03]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:5680kb
  • [2024-10-16 15:50:02]
  • 提交

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) {
//                    dfs((v + 1) % n, !flag);
//                }
//                else {
//                    ans[(v + 1) % n] = !flag;
//                }
//                if (st.count((v - 1 + n) % n) != 0) {
//                    dfs((v - 1 + n) % n, !flag);
//                }
//                else {
//                    ans[(v - 1 + n) % n] = !flag;
//                }
//            }
//        }
//        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<char>ans(n, '0');
//        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);
//        }		x	1	__int64
//
//        char p;
//        // int i = *(st.begin()), sum = 1;
//        // for (;sum<=n; i=(i+1)%n)
//        // {
//        //     sum++;
//        //     if (ans[i] == '0')
//        //     {
//        //         ans[i] = (p == 'R' ? 'B' : 'R');
//        //     }
//        //     p = ans[i];
//        // }
//        for (int i = 0; i < n; i++) {
//            cout << (ans[i] == -1 ? 'R' : (ans[i] == 0 ? 'R' : 'B'));
//            e[i].clear();
//        }
//
//        cout << endl;
//
//    }
//    return 0;
//}

#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)
            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;
        }
        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)
            {
                if (ans[((i - 1) % n + n) % n] != -1)
                    dfs(i, 1 - ans[((i - 1) % n + n) % n]);
                else if (ans[(i + 1) % n] != -1)
                    dfs(i, 1 - ans[(i + 1) % n]);
                else
                    dfs(i, 0);
            }
        }
        char p;
        int i = *(st.begin()), sum = 1;
        for (; sum <= n; i = (i + 1) % n)
        {
            sum++;
            if (ans[i] == -1)
            {
                ans[i] = 1 - p;
            }
            p = ans[i];
        }
        for (int i = 0; i < n; i++) {
            cout << (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: 5680kb

input:

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

output:

BRB
RRBB
RBBRRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 62ms
memory: 3692kb

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:

RBBBBRRBR
BRB
RBBRR
RRRBBB
RRBBBRRBB
BRB
RRBBBRR
RRBBBBR
RRBB
RBRBBR
RRBBRR
RRRRBBR
RRBBBBRR
BRB
RBBBRBBR
RRBBBBRR
BRB
RBBBBBBRRR
RRBRRBBB
RRRRRRBBBB
RRRRRBBBBB
RBBBRBBBRR
BRB
RRBRRBB
RRBBBB
RBBRRRRR
RRBB
RBBBRRR
RRRRRBBBBB
RRRRBBB
RRBRRBBB
RRBBBB
RBBRRB
BRB
BRB
RRBBBRRRB
RRRBBRR
RRBBR
BRRRBBBRRR
RR...

result:

wrong answer cycle detected (test case 47)