QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644914#8544. Colorful Graph 2asaltfishWA 70ms5856kbC++234.9kb2024-10-16 15:59:532024-10-16 15:59:55

Judging History

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

  • [2024-10-16 15:59:55]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:5856kb
  • [2024-10-16 15:59:53]
  • 提交

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 bfs(ll x, bool flag)
{
    deque<ll>q;
    ans[x] = flag;
    q.push_back(x);
    while (q.size())
    {
        ll now = q.front();
        q.pop_front();
        for (auto i : e[now])
        {
            if (ans[i] == -1)
            {
                ans[i] = 1 - flag;
                q.push_back(i);
            }
        }
    }
}
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)
            {
                bfs(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;
}

詳細信息

Test #1:

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

input:

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

output:

BRB
RRBB
RBBRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 70ms
memory: 3540kb

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:

RBBBBRBBR
BRB
RBBRB
RRBRBB
RRBBBRBRB
BRB
RBRBBRB
RBRBBBR
RRBB
RBBRBR
RBRBRB
RBBBRBR
RBRBBBRB
BRB
RBBBBRBR
RBRBBBRB
BRB
RBBBBBBRBB
RRBBBRBB
RRBBBBRBBB
RRBBBRBBBB
RBBBBRBBRB
BRB
RRBRBRB
RRBBBB
RBBRBBBB
RRBB
RBBBRBB
RRBBBRBBBB
RRBBRBB
RRBRBRBB
RRBBBB
RBBRBR
BRB
BRB
RRBBBRBBB
RBBRBRB
RBRBR
RRBBRBBRBB
RB...

result:

wrong answer cycle detected (test case 1)