QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310744#8128. Alternating PathsKevin5307WA 608ms3820kbC++232.2kb2024-01-21 17:21:402024-01-21 17:21:40

Judging History

你现在查看的是最新测评结果

  • [2024-01-21 17:21:40]
  • 评测
  • 测评结果:WA
  • 用时:608ms
  • 内存:3820kb
  • [2024-01-21 17:21:40]
  • 提交

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)