QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689613 | #8544. Colorful Graph 2 | szy10010# | WA | 49ms | 17896kb | C++23 | 2.4kb | 2024-10-30 17:58:25 | 2024-10-30 17:58:27 |
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;
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)