QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310738#8128. Alternating PathsKevin5307WA 604ms3820kbC++232.1kb2024-01-21 17:20:192024-01-21 17:20:19

Judging History

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

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

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)