ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206792 | #3693. 染色 1 | ZQ202209 | 100 | 1899ms | 15768kb | C++ | 932b | 2024-07-25 18:04:49 | 2024-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"