QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689928 | #8544. Colorful Graph 2 | szy10010# | WA | 42ms | 18092kb | C++23 | 2.5kb | 2024-10-30 19:16:47 | 2024-10-30 19:16:47 |
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;
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)