QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689613#8544. Colorful Graph 2szy10010#WA 49ms17896kbC++232.4kb2024-10-30 17:58:252024-10-30 17:58:27

Judging History

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

  • [2024-10-30 17:58:27]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:17896kb
  • [2024-10-30 17:58:25]
  • 提交

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;
        return dfs(j,u);
    }
    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<=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);
    }
    for(int i=0;i<m;i++)
    {
        int x = i+1,y=(i+2)%m;
        if(st[x]&&st[y]) addd(x,y);
    }
    
    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: 0ms
memory: 17888kb

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: 49ms
memory: 17896kb

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
Impossible
RBRRRRBRR
RRB
RRRBBRR
Impossible
RRRB
RRBRBR
RRRBRR
RRRRRBR
Impossible
RRB
BRRRRRBR
Impossible
RRB
RRBRRRRRBR
Impossible
Impossible
RBRRRRBRRR
Impossible
RRB
RRRRBRB
RBRRRR
RRBRRRRR
RRRB
Impossible
Impossible
RRRRRBB
RBRRBRRR
RBRRRR
Impossible
RRB
RRB
Impossible
RRRRBR...

result:

wrong answer Token parameter [name=S] equals to "Impossible", doesn't correspond to pattern "[BR]{1,200000}" (test case 4)