QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689595 | #8544. Colorful Graph 2 | szy10010# | WA | 0ms | 17876kb | C++23 | 2.4kb | 2024-10-30 17:53:36 | 2024-10-30 17:53:36 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)