QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689928#8544. Colorful Graph 2szy10010#WA 42ms18092kbC++232.5kb2024-10-30 19:16:472024-10-30 19:16:47

Judging History

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

  • [2024-10-30 19:16:47]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:18092kb
  • [2024-10-30 19:16:47]
  • 提交

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  = 1e6+10;
int tr[N];
int du[N];
int m,n;
pii ed[N];
int st[N],stt[N];
int h[N],e[N],ne[N],idx;
//
int lowbit(int x){
    return x&-x;
}

void add(int x,int c){
    for(int i=x;i<=m;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

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=0;
    for(int i=1;i<=4*m;i++)
    {
        du[i]=tr[i]=stt[i]=st[i]=0;
        h[i]=-1;
    }
}
//


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++;
        du[a]++,du[b]++;
        ed[i]={a,b};
    }
    int now = 0;
    for(int i=1;i<=n;i++)
    {
        int x =ed[i].f,y=ed[i].s;
        du[x]--,du[y]--;
        if(x>y) swap(x,y);
        if(st[x]||st[y]) continue;
        int su= sum(y-1)-sum(x);
        if(su>0&&su!=now) continue;
        int nn;
        if(du[x]>du[y]) nn=x;
        else nn=y;
        st[nn]=1;
        add(nn,1);
        now++;
    }
    string res;
    for(int i=1;i<=n;i++)
    {
        int x =ed[i].f,y=ed[i].s;
        if(st[x]&&st[y]) addd(x,y),addd(y,x);
    }
    for(int i=0;i<m;i++)
    {
        int x = i+1,y=(i+2)%m;
        if(st[x]&&st[y]) 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]) 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: 2ms
memory: 17860kb

input:

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

output:

RRB
RRRB
RRBRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 42ms
memory: 18092kb

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:

BRRRRRBRR
RRB
RRBRR
RBRRBR
RBRRRRBRR
RRB
RRRBBRR
RBRRRBR
RRRB
RRBRBR
RRRBRR
RRRRRBR
RBRRRBRR
RRB
BRRRRRBR
RBRRRBRR
RRB
RRBRRRRRBR
RBRRRRBR
RRRRRBRRBB
RBRRRRBRRR
BRRRBRRBRR
RRB
RRRRBRB
RBRRRR
RRBRRRRR
RRRB
RRBRRBB
RRBRRRBRRB
RRRRRBB
RBRRBRRR
RBRRRR
RRBRBR
RRB
RRB
RBRRRRBBR
RRRRBRR
RRRBR
RRRRRBRRBB
RR...

result:

wrong answer cycle detected (test case 18)