QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310744 | #8128. Alternating Paths | Kevin5307 | WA | 608ms | 3820kb | C++23 | 2.2kb | 2024-01-21 17:21:40 | 2024-01-21 17:21:40 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int u[303],v[303];
int n,m;
int c[303];
mt19937 rnd(20210448);
vector<pii> G[105];
bool vis[105];
void dfs(int u,int d=0)
{
vis[u]=1;
for(auto pr:G[u])
if(!vis[pr.first])
{
c[pr.second]=d;
dfs(pr.first,d^1);
}
}
void color()
{
memset(vis,0,sizeof(vis));
memset(c,-1,sizeof(c));
dfs(rnd()%n+1,0);
for(int i=1;i<=m;i++)
if(c[i]==-1)
c[i]=rnd()%2;
}
bitset<256> E[256];
bool check()
{
for(int i=1;i<=n+n;i++)
E[i]=0;
for(int i=1;i<=m;i++)
E[c[i]*n+u[i]][(c[i]^1)*n+v[i]]=E[c[i]*n+v[i]][(c[i]^1)*n+u[i]]=1;
for(int i=1;i<=n;i++)
{
bitset<256> cur;
queue<int> q;
q.push(i);
q.push(n+i);
cur[i]=cur[n+i]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
bitset<256> bs=E[x]^(E[x]&cur);
cur|=bs;
int p=bs._Find_first();
while(p<=n+n)
{
q.push(p);
p=bs._Find_next(p);
}
}
for(int j=1;j<=n;j++)
if(!cur[j]&&!cur[j+n])
return false;
}
return true;
}
void solve()
{
for(int i=1;i<=n;i++)
G[i].clear();
for(int i=1;i<=m;i++)
{
G[u[i]].pb(v[i],i);
G[v[i]].pb(u[i],i);
}
int threshold=30000;
while(threshold--)
{
color();
if(check())
{
for(int i=1;i<=m;i++)
putchar(c[i]?'R':'B');
putchar(10);
return ;
}
}
puts("IMPOSSIBLE");
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>u[i]>>v[i];
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3620kb
input:
3 6 6 1 2 2 3 3 1 4 1 5 2 6 3 6 6 1 2 2 3 3 1 3 4 4 5 4 6 4 3 1 2 4 2 2 3
output:
BRBRBB BRRBRR IMPOSSIBLE
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 4 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
BRBRBB
result:
ok ok (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 5 6 1 2 1 3 1 5 2 4 2 5 3 4
output:
BRBRRB
result:
ok ok (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1 5 8 1 2 1 4 1 5 2 3 2 4 2 5 3 4 4 5
output:
BRBRBRBR
result:
ok ok (1 test case)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 7 12 1 2 1 3 1 6 2 3 2 5 2 7 3 4 3 5 3 6 4 6 4 7 5 7
output:
RBRBBBRRRBBB
result:
ok ok (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1 7 13 1 2 1 3 1 4 1 6 1 7 2 5 3 5 3 7 4 6 4 7 5 6 5 7 6 7
output:
RBRBBBRRRBRBR
result:
ok ok (1 test case)
Test #7:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
1 4 5 1 2 1 3 1 4 2 3 2 4
output:
BRBRR
result:
ok ok (1 test case)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 5 7 1 2 1 4 2 3 2 4 3 4 3 5 4 5
output:
BRRBBBR
result:
ok ok (1 test case)
Test #9:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 5 7 1 2 1 5 2 3 2 5 3 4 3 5 4 5
output:
BRRBBBR
result:
ok ok (1 test case)
Test #10:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 6 6 1 2 1 4 2 3 2 6 3 5 4 5
output:
RBBBBR
result:
ok ok (1 test case)
Test #11:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 6 10 1 2 1 3 1 5 1 6 2 4 3 4 3 5 3 6 4 5 4 6
output:
RBRBBBRRRR
result:
ok ok (1 test case)
Test #12:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 9 14 1 2 1 5 1 8 2 3 2 4 3 6 3 9 4 6 4 7 4 8 5 7 5 8 6 8 7 8
output:
RBRBBRBRBRRBBB
result:
ok ok (1 test case)
Test #13:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 7 12 1 2 1 3 1 4 1 6 1 7 2 5 2 7 3 4 3 6 3 7 4 5 5 6
output:
RRBBRBBBRRRB
result:
ok ok (1 test case)
Test #14:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
1000 2 1 2 1 2 1 1 2 2 1 2 1 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1...
output:
B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B ...
result:
ok ok (1000 test cases)
Test #15:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
1000 2 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 2 1 2 1 2 1 1 2 2 1 1 2...
output:
B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B ...
result:
ok ok (1000 test cases)
Test #16:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
1000 3 3 2 1 1 3 3 2 3 2 3 1 3 2 3 3 2 3 2 1 3 1 3 2 2 1 3 2 3 3 2 3 3 1 1 2 3 3 1 3 2 1 2 3 3 3 2 1 3 2 3 1 3 3 1 3 1 2 3 2 3 3 3 1 2 1 3 2 3 3 1 3 1 2 3 2 3 2 3 1 1 2 3 3 3 2 1 3 1 2 3 2 3 1 2 1 3 3 3 2 1 2 3 1 3 3 2 1 3 2 1 3 3 3 1 2 3 2 1 3 3 3 3 1 3 2 2 1 3 3 1 2 3 2 3 1 3 3 1 2 2 3 3 1 3 2 2 3...
output:
RBR BR BBR RB BBR RBR BRB BRR RBR BRR BR RBB BR BRR RBB BBR RBB BRR BBR BR BR BR BR RBB RB BRR RBR RB RBB RBB RBR BRB BR RB BR RBR RB BRB BRB RB BR RB BRR BRR BBR BR RB BRB BR RBR BR BR BRR BBR RB BR RB RB BRR BR RB BR BBR BR RB RBB BR BBR RB BR BBR RBB BRR BR BBR RB BRR BR BR BR BR RBB BR BRR BR BR...
result:
ok ok (1000 test cases)
Test #17:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
1000 3 3 3 2 2 1 3 1 3 2 1 3 2 1 3 2 1 2 3 2 3 3 3 1 1 2 2 3 3 2 3 1 2 3 3 3 1 2 1 3 2 3 3 2 1 3 3 2 3 3 2 3 3 1 1 2 3 3 3 1 2 1 2 3 3 2 1 3 3 2 3 3 2 3 1 3 2 1 3 2 2 1 3 1 3 3 3 1 1 2 3 2 3 3 3 1 3 2 2 1 3 2 1 3 2 3 3 2 3 2 2 1 3 3 1 3 1 2 3 2 3 3 2 1 1 3 3 2 3 2 1 3 1 2 3 3 2 1 3 1 2 3 3 3 3 2 1 2...
output:
BRR BR RB BRR BR RBR RB RBB BRR BR BRR RB BRB BRR RB RB BRB BRB RB BRR BBR BRR BR BR RB BR BR BBR BRR BRR BR BR RB BR BR RBB RB RBB RBR RB BRR BR BRR BRR BRR BR BRR BR BBR RBR BR RB BRR BRB BRR BRB RBB BR BRB BBR BR RBB RBR RBR BRB BR RB BRR BR BRR BRR BR RBR BRR BR RB BBR BR BRR RBB BBR BRB RBR BR ...
result:
ok ok (1000 test cases)
Test #18:
score: 0
Accepted
time: 447ms
memory: 3576kb
input:
1000 4 4 2 1 4 2 3 2 1 3 4 4 2 1 1 4 2 4 2 3 4 5 1 3 2 4 1 2 1 4 3 2 4 3 3 4 1 4 4 2 4 6 1 4 3 1 4 2 1 2 4 3 3 2 4 3 1 3 4 3 2 3 4 3 3 2 4 2 2 1 4 5 1 3 2 4 4 3 2 3 1 4 4 4 1 4 3 2 3 4 2 1 4 6 3 4 4 2 2 1 4 1 1 3 3 2 4 6 4 2 1 4 2 3 4 3 2 1 3 1 4 6 4 1 3 4 3 2 3 1 2 1 4 2 4 6 4 1 2 4 2 1 1 3 3 2 3 4...
output:
BRRR RBRB BBRRR IMPOSSIBLE BRRBBB IMPOSSIBLE IMPOSSIBLE BBRBR BBRB BBBBRB BBRBRB BRBRRR RBRBBR BRBB RBB RBBBBR BRBB RBBB BRB BRBBR RBBBR BRRR BRBBBB BRBRB BBR RBBRBB BBRRBR BRRRBB RBRBBB RRBBB BRBBBB BBRRR RBB IMPOSSIBLE BRBB RBRB RBB RBBB RBRBBB IMPOSSIBLE RBB BBRBR IMPOSSIBLE IMPOSSIBLE BRBRRB BBR...
result:
ok ok (1000 test cases)
Test #19:
score: 0
Accepted
time: 530ms
memory: 3628kb
input:
1000 4 6 4 2 4 1 3 4 3 1 1 2 3 2 4 3 4 2 3 2 1 3 4 6 4 3 1 2 2 3 1 3 2 4 4 1 4 4 2 1 3 1 4 1 3 2 4 5 2 4 1 2 1 3 4 1 3 2 4 3 2 3 2 4 1 4 4 4 1 2 3 2 1 4 2 4 4 5 2 1 1 3 3 2 4 1 4 2 4 4 1 2 4 2 3 2 4 1 4 6 2 4 3 4 3 2 3 1 4 1 1 2 4 3 1 3 2 4 3 2 4 6 4 3 4 1 2 1 4 2 3 1 3 2 4 4 1 2 4 3 1 3 2 3 4 6 3 2...
output:
RBRBBB BRB BBRBRR RBRR BRBBB BRB RBBB RBBBB RRBB BRRBBB BBR BRBRBR BBRB RBBRBR BRBRR IMPOSSIBLE BRBBRB RBBB RBBRB RBBBR BRB RBBRB BBBRRR BRBRB BBRBBB BRRBB BRBBR BBRB BBBRBR BBRB RBBBBR RBRR BBRBRB BRB BRBRB IMPOSSIBLE RBBRB BRRR RBBRRR BRBR RBBB BBBRBB RBB RBBBR BRBRRR BBR IMPOSSIBLE RBRB BRB RBBBB...
result:
ok ok (1000 test cases)
Test #20:
score: -100
Wrong Answer
time: 608ms
memory: 3612kb
input:
1000 5 8 5 1 4 5 2 4 3 2 2 1 5 3 1 3 3 4 5 9 2 4 4 5 5 2 1 5 3 1 3 5 4 1 4 3 1 2 5 5 1 4 3 1 1 5 5 2 4 2 5 9 1 2 5 4 4 3 4 2 4 1 5 3 1 5 5 2 2 3 5 9 3 4 3 2 2 5 3 1 4 5 5 3 4 1 1 5 4 2 5 10 3 5 2 1 2 5 5 4 1 3 4 2 1 4 5 1 2 3 4 3 5 5 3 4 5 3 5 1 5 4 2 5 5 6 1 2 2 4 1 5 3 2 3 1 3 4 5 8 4 2 4 3 1 2 1 ...
output:
BRBRRBBR BRBBRRRBR BBRBR BBBRRRBRB RBBRBBRRB BBBBRRRBRR BRBRB RBBBBR RBBBBRRR RBBR RRBBBBRBB BBRRR BBRBRB BRBRR RRBBRRBRBR IMPOSSIBLE BBRBRBRBB BBBBRB BRRBBR BRBBBRRBBR IMPOSSIBLE RBRBBRB BRRBRB RBRRRRRBBB BRBRRRRBR IMPOSSIBLE RBRRBRBRBB RBRBBRBB RBBBBRRBBR IMPOSSIBLE BRBRBBBRRR RRRRBBBRR BRRBRBBBB ...
result:
wrong answer jury has answer but participant doesn't (test case 16)