UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206792#3693. 染色 1ZQ2022091001899ms15768kbC++932b2024-07-25 18:04:492024-07-25 20:04:00

answer

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int N=2e5+1;
vector<long long> g[N];
bool flag=true;
long long a,b,u,v,sum=1;
short vis[N];
void get(long long id,long long fa)
{
	if(!flag)return ;
	for(int i=0;i<g[id].size();i++)
	{
		if(g[id][i]!=fa)
		{
			if(vis[g[id][i]]==0)
			{
				vis[g[id][i]]=vis[id]==1?2:1;
				get(g[id][i],id);
			}
			if(vis[g[id][i]]==vis[id])
			{
//				cout<<vis[g[id][i]]<<" "<<g[id][i]<<" "<<id<<"\n";
				flag=false;
				return ;
			}
		}
	}
	return ;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	for(int i=1;i<=b;i++)
	{
		scanf("%lld%lld",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=a;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;
			get((long long)i,(long long)i);
			sum=(sum*2)%998244353;
		}
		if(flag==false)
		{
			printf("0");
			return 0;
		}
	}
	printf("%lld",sum);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 5920kb

input:

20 10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

output:

1024

result:

ok "1024"

Test #2:

score: 5
Accepted
time: 0ms
memory: 5936kb

input:

20 33
6 9
16 12
10 15
13 19
17 18
3 5
14 10
18 6
12 5
14 3
20 11
5 7
11 10
20 15
11 3
20 16
9 8
16 3...

output:

2

result:

ok "2"

Test #3:

score: 5
Accepted
time: 4ms
memory: 5928kb

input:

20 4
1 2
2 3
3 4
4 1

output:

131072

result:

ok "131072"

Test #4:

score: 5
Accepted
time: 0ms
memory: 5912kb

input:

20 44
1 7
4 8
16 11
6 17
11 13
19 10
5 4
6 20
12 20
7 18
2 14
2 4
14 16
8 7
12 6
12 15
12 19
19 16
1...

output:

0

result:

ok "0"

Test #5:

score: 5
Accepted
time: 0ms
memory: 6268kb

input:

200000 0

output:

792253081

result:

ok "792253081"

Test #6:

score: 5
Accepted
time: 14ms
memory: 7452kb

input:

200000 20000
174989 72342
29431 82489
134989 16335
195898 6766
44379 166973
63575 179953
56568 25387...

output:

591782332

result:

ok "591782332"

Test #7:

score: 5
Accepted
time: 40ms
memory: 8404kb

input:

200000 40000
130141 81160
183643 55620
127442 59859
108045 119463
53388 131934
165208 164601
175718 ...

output:

342500594

result:

ok "342500594"

Test #8:

score: 5
Accepted
time: 64ms
memory: 9216kb

input:

200000 60000
171595 53259
39846 120035
194218 185176
199578 128587
109637 186890
61191 149114
13490 ...

output:

449711975

result:

ok "449711975"

Test #9:

score: 5
Accepted
time: 81ms
memory: 9908kb

input:

200000 80000
187748 73706
15086 125096
41903 104401
116412 136210
65816 36448
193171 181724
132712 1...

output:

488189483

result:

ok "488189483"

Test #10:

score: 5
Accepted
time: 93ms
memory: 10536kb

input:

200000 99999
82325 170581
135463 7992
6832 37354
182855 12267
22716 105436
193084 100744
23038 13949...

output:

78278423

result:

ok "78278423"

Test #11:

score: 5
Accepted
time: 134ms
memory: 11368kb

input:

200000 119999
6165 92447
96033 58454
123842 66763
165430 17518
10165 19222
81965 119810
139780 71394...

output:

252055733

result:

ok "252055733"

Test #12:

score: 5
Accepted
time: 150ms
memory: 12432kb

input:

200000 139998
82113 88641
95759 69269
8316 145629
47 53984
170614 123587
117656 184230
577 63209
111...

output:

462026080

result:

ok "462026080"

Test #13:

score: 5
Accepted
time: 171ms
memory: 13560kb

input:

200000 159998
66716 121827
80674 122443
43128 28295
21904 164099
155673 181760
65574 49206
9370 1037...

output:

269680017

result:

ok "269680017"

Test #14:

score: 5
Accepted
time: 190ms
memory: 14696kb

input:

200000 180000
38840 146514
83106 155855
95948 59635
2672 180633
46476 32494
17665 128504
39486 79516...

output:

965754317

result:

ok "965754317"

Test #15:

score: 5
Accepted
time: 108ms
memory: 15768kb

input:

200000 199999
74181 148298
172708 84122
128717 191784
145066 169886
97568 4822
41662 106531
155190 1...

output:

400146199

result:

ok "400146199"

Test #16:

score: 5
Accepted
time: 146ms
memory: 13364kb

input:

200000 199999
26174 152764
68298 125193
94893 95074
160078 127091
139840 76057
67459 51195
144214 16...

output:

0

result:

ok "0"

Test #17:

score: 5
Accepted
time: 176ms
memory: 13328kb

input:

200000 200000
49288 149508
16008 106916
154117 48928
185344 66024
110881 86068
108409 129286
3267 20...

output:

0

result:

ok "0"

Test #18:

score: 5
Accepted
time: 156ms
memory: 13356kb

input:

200000 199995
76537 52199
163353 74374
6227 51113
126883 46291
180849 124164
75589 93348
168981 8843...

output:

0

result:

ok "0"

Test #19:

score: 5
Accepted
time: 191ms
memory: 13356kb

input:

200000 199998
105389 154107
18088 61057
11136 103748
6361 47540
18612 173030
72837 73696
3808 138264...

output:

0

result:

ok "0"

Test #20:

score: 5
Accepted
time: 181ms
memory: 13372kb

input:

200000 199999
167802 125259
194020 186636
11474 133555
22188 83709
14389 67107
198734 53893
21509 33...

output:

0

result:

ok "0"