QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689931#8544. Colorful Graph 2szy10010#WA 73ms17928kbC++232.8kb2024-10-30 19:18:232024-10-30 19:18:24

Judging History

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

  • [2024-10-30 19:18:24]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:17928kb
  • [2024-10-30 19:18:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int> 
#define f first 
#define s second
#define int long long



//
const int N  = 2e6+10;
int tr[N];
int du[N],idx1;
int m,n;
pii ed[N];
int st[N],stt[N];
int h[N],e[N],ne[N],idx,h1[N];
//

void add(int a,int b){
    ne[idx1]=h1[a],e[idx1]=b,h1[a]=idx1++;
}
bool dfs(int u,int fa)
{
    stt[u]=1;
    
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        if(stt[j]) return 0;
        if(!dfs(j,u)) return 0;
    }
    return 1;
}


void addd(int a,int b)
{
    ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}

void init()
{
    idx=idx1=0;
    for(int i=1;i<=4*m;i++)
    {
        du[i]=stt[i]=st[i]=0;
        h1[i]=h[i]=-1;
    }
}
void bfs(int u)
{
    queue<int>qu;
    st[u]=1;
    qu.push(u);
    while(qu.size())
    {
        int t = qu.front();
        qu.pop();
        for(int i=h1[t];~i;i=ne[i])
        {
            int j=e[i];
            if(st[j]) continue;
            st[j]=3-st[t];
            qu.push(j);
        }
    }
}
//


void solve()
{
    cin>>m>>n;
    if(!n)
    {
        for(int i=1;i<=m-1;i++) cout<<"R";
        cout<<"B"<<endl;
        return ; 
    }
    init();
    
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        a++,b++;
        ed[i]={a,b};
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=m;i++)
        if(!st[i]) bfs(i);
    string res;
    for(int i=1;i<=n;i++)
    {
        int x =ed[i].f,y=ed[i].s;
        if(st[x]==1&&st[y]==1) addd(x,y),addd(y,x);
    }
    for(int i=0;i<m;i++)
    {
        int x = i+1,y=(i+2)%m;
        if(st[x]==1&&st[y]==1) addd(x,y),addd(y,x);
    }
    for(int i=1;i<=m;i++)
        if(!stt[i]) 
        {
            if(!dfs(i,-1)) 
            {
                cout<<"Impossible"<<endl;
                return ;
            }
        }
    for(int i=1;i<=n;i++)
    {
        int x =ed[i].f,y=ed[i].s;
        if(st[x]==2&&st[y]==2) addd(x,y),addd(y,x);
    }
    for(int i=0;i<m;i++)
    {
        stt[i+1]=0;
        int x = i+1,y=(i+2)%m;
        if(st[x]==2&&st[y]==2) addd(x,y),addd(y,x);
    }
    for(int i=1;i<=m;i++)
        if(!stt[i]) 
        {
            if(!dfs(i,-1)) 
            {
                cout<<"Impossible"<<endl;
                return ;
            }
        }
    
    for(int i=1;i<=m;i++)
    {
        if(st[i]==1) res.push_back('B');
        else res.push_back('R');
    }
    cout<<res<<endl;
}
signed main()
{
    IOS;
    int _=1;
    cin>>_;
    while(_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

RRB
BBBR
BBRBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 73ms
memory: 17884kb

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:

BBRBBBRRB
RRB
BBRBB
BBBBRR
BBBRBBRBR
RRB
BBBRRBB
BBBRRRB
BBBR
BBRBRB
BBBRBB
BBBBBRB
BBBRRRBB
RRB
BBRRRBRB
BBBRRRBB
RRB
BBRRRRRBBB
BBBRBBRR
BBBBBBBRRR
BBBBBBRRRR
BBRRRBBBBB
RRB
BBBBRBR
BBBRRR
BBRBBBBB
BBBR
BBRRBBB
BBBBBBRRRR
BBBBBRR
BBBBRBRR
BBBRRR
BBRBRB
RRB
RRB
BBBRRBBRR
BBBBRBB
BBBRB
BBBBBRBBRR
BB...

result:

wrong answer cycle detected (test case 22)