ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206773 | #3693. 染色 1 | one_zero_four_zero | 100 | 1556ms | 14728kb | C++11 | 839b | 2024-07-25 17:44:31 | 2024-07-25 20:02:24 |
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n, m;
int u, v;
long long ans = 1, mod = 998244353;
int col[200005];
vector<int> E[200005];
void dfs(int u, int c){
col[u] = c;
for (auto && i : E[u]){
if (col[i] == col[u]){
printf("0\n");
exit(0);
}
if (col[i]) continue;
dfs(i, 3 - c);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("../data.in","r",stdin);
freopen("../data.out","w",stdout);
#endif
scanf("%d %d", &n, &m);
while (m --){;
scanf("%d %d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
}
for (int i = 1; i <= n; i ++){
if (col[i]) continue;
dfs(i, 1);
ans = (ans * 2) % mod;
}
printf("%lld\n", ans % mod);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 5912kb
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: 5928kb
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: 0ms
memory: 5928kb
input:
20 4 1 2 2 3 3 4 4 1
output:
131072
result:
ok "131072"
Test #4:
score: 5
Accepted
time: 2ms
memory: 5916kb
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: 6660kb
input:
200000 0
output:
792253081
result:
ok "792253081"
Test #6:
score: 5
Accepted
time: 21ms
memory: 7840kb
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: 46ms
memory: 8772kb
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: 55ms
memory: 9536kb
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: 89ms
memory: 10148kb
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: 101ms
memory: 10668kb
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: 131ms
memory: 11356kb
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: 159ms
memory: 12256kb
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: 174ms
memory: 13168kb
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: 192ms
memory: 13992kb
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: 171ms
memory: 14728kb
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: 72ms
memory: 12320kb
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: 96ms
memory: 12292kb
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: 100ms
memory: 12308kb
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: 76ms
memory: 12324kb
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: 71ms
memory: 12344kb
input:
200000 199999 167802 125259 194020 186636 11474 133555 22188 83709 14389 67107 198734 53893 21509 33...
output:
0
result:
ok "0"