QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#689595#8544. Colorful Graph 2szy10010#WA 0ms17876kbC++232.4kb2024-10-30 17:53:362024-10-30 17:53:36

Judging History

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

  • [2024-10-30 17:53:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:17876kb
  • [2024-10-30 17:53:36]
  • 提交

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

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 17876kb

input:

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

output:

RRB
RRBR
RBRBRR

result:

wrong answer cycle detected (test case 2)