QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310738 | #8128. Alternating Paths | Kevin5307 | WA | 604ms | 3820kb | C++23 | 2.1kb | 2024-01-21 17:20:19 | 2024-01-21 17:20:19 |
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(114514);
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:
RBBBBR BRRBRR IMPOSSIBLE
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 4 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
RRBBRR
result:
ok ok (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
1 5 6 1 2 1 3 1 5 2 4 2 5 3 4
output:
RRBBRR
result:
ok ok (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 5 8 1 2 1 4 1 5 2 3 2 4 2 5 3 4 4 5
output:
RRBBRRRB
result:
ok ok (1 test case)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
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:
RBRRRBRRBBRB
result:
ok ok (1 test case)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3488kb
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:
RRRRBBRBBRRBB
result:
ok ok (1 test case)
Test #7:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 4 5 1 2 1 3 1 4 2 3 2 4
output:
RRBBR
result:
ok ok (1 test case)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
1 5 7 1 2 1 4 2 3 2 4 3 4 3 5 4 5
output:
BRRRRBR
result:
ok ok (1 test case)
Test #9:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 5 7 1 2 1 5 2 3 2 5 3 4 3 5 4 5
output:
RBBRRRR
result:
ok ok (1 test case)
Test #10:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 6 6 1 2 1 4 2 3 2 6 3 5 4 5
output:
RBRBBR
result:
ok ok (1 test case)
Test #11:
score: 0
Accepted
time: 0ms
memory: 3820kb
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:
RRRBBRBRBR
result:
ok ok (1 test case)
Test #12:
score: 0
Accepted
time: 0ms
memory: 3492kb
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:
BRRRRBRRRBBBRB
result:
ok ok (1 test case)
Test #13:
score: 0
Accepted
time: 0ms
memory: 3776kb
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:
RRRRBBBBRRRB
result:
ok ok (1 test case)
Test #14:
score: 0
Accepted
time: 1ms
memory: 3540kb
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: 3532kb
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: 3552kb
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 RB BRR RB BRR BRB BBR BBR RBR BRB RB RBB RB RBR BRR RBR BBR RBR BRR RB BR BR BR RBB RB BBR BRR BR RBB BRB RBB BRB BR BR BR BBR BR BRB BRR RB RB RB BRB BRR RBB RB BR RBR RB RBR RB BR BBR BRR BR RB BR RB BRR BR BR BR BRB RB BR RBR RB RBB RB BR BRR RBB RBB RB RBR RB BBR RB RB BR RB BRR BR RBR BR BR...
result:
ok ok (1000 test cases)
Test #17:
score: 0
Accepted
time: 1ms
memory: 3532kb
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 BRB RB BRR BR BRB BBR RB BRR BR RBR BBR BR RB RBR RBR BR BRB RBR BRB BR BR BR BR BR RBB BBR RBB RB RB BR RB BR RBB RB BRR RBR BR BBR RB BBR RBB BRR BR BRR BR BRB BBR BR RB BBR RBB BRR BRR BBR RB BRB BRR RB BRR BBR RBB BRR RB BR RBB BR RBR BRR RB BBR RBR BR RB BBR RB BRR BRR BRB BRR BBR RB ...
result:
ok ok (1000 test cases)
Test #18:
score: 0
Accepted
time: 449ms
memory: 3744kb
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:
RBRB RBRB BBRRB IMPOSSIBLE BBRRBB IMPOSSIBLE IMPOSSIBLE BBBRB BBRB BBBRRB RBBRBB BRBRRB BRRBBR BRRB RBB BBRBBR BRBB RBBR BRB BBBBR RBBBB RBBB BRBBBB RBBBB BBR BRRBBB BBRRRR BRBBBR RBRBBR BRRBB RBRBRR BBRBR RBB IMPOSSIBLE BRBB RBBB RBB RBRB RBBBBR IMPOSSIBLE RBB BBRRR IMPOSSIBLE IMPOSSIBLE BBRRRB BBR...
result:
ok ok (1000 test cases)
Test #19:
score: 0
Accepted
time: 525ms
memory: 3532kb
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:
BRRBRR BRB BBBRRR RRBB RBRRR BRB BRRR BRRRR BRRR BRRBBR BBR BRBBBR BBRR BBRBBB RBBBB IMPOSSIBLE BBRRRB RBRB RBBRB RBBRR BRB RBRBB BBRRRB RBRBR RBBRBB BRBBB BRRBR BBRR BBRRBR RBBB RBBRBB BRRB BBRRBR BRB BBBRB IMPOSSIBLE BRRBB RBBB RBBBBR BRBR BRRR BRBBRB RBB BRBRR BBBRBB BBR IMPOSSIBLE RBBB BRB RBBBB...
result:
ok ok (1000 test cases)
Test #20:
score: -100
Wrong Answer
time: 604ms
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:
BRBRRRBR RBBBRRRBB RRBRB BBBRRRRBB RBRRBRRRR BBRBBRRRRB BRBRB BBRRRB BBRBBBBR RBBR RRBRBRBRB BBRRR BBRBRR BRBRR BBRBRBBRRB IMPOSSIBLE BRRRBBBRB BBRRRB BRRBRB BRBRRBBRRR IMPOSSIBLE BBBRBBB BRBBBR BBBRRRRBRR RBRRRRBRR IMPOSSIBLE BRBRRBBBBB BBBRRBBR RBRBBBBRRR IMPOSSIBLE BBBRBRRBRB BBBBRBRBR BRRBRRRRR ...
result:
wrong answer jury has answer but participant doesn't (test case 16)