QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644867#8544. Colorful Graph 2DukerkiML 1ms5708kbC++202.5kb2024-10-16 15:43:502024-10-16 15:43:51

Judging History

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

  • [2024-10-16 15:43:51]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:5708kb
  • [2024-10-16 15:43:50]
  • 提交

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;
                }
            }
            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;
        // 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;
}

详细

Test #1:

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

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
Memory Limit Exceeded

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:


result: