QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #419 | #216030 | #6501. Graph Partitioning | pskkk | levitated | Success! | 2023-11-04 12:30:34 | 2023-11-04 12:30:34 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 3948kb
input:
5 1 2 1 3 1 4 2 3 2 4 3 4 1 2 4 5
output:
4
result:
wrong answer 1st numbers differ - expected: '0', found: '4'
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #216030 | #6501. Graph Partitioning | levitated | WA | 164ms | 7728kb | C++14 | 601b | 2023-10-15 15:17:55 | 2023-11-04 12:36:02 |
answer
//qoj6501
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, fa[N];
int gf(int x){
return x == fa[x] ? x : fa[x] = gf(fa[x]);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n+n-2; ++ i){
fa[i] = i;
}
for(int i = 1; i <= n+n-2; ++ i){
int u, v;
scanf("%d%d", &u, &v);
if(u == v){
puts("0");
return 0;
}
if(u > v){
swap(u, v);
}
fa[gf(u)] = gf(v+n-2);
}
long long ans = 1;
for(int i = 1; i <= n+n-2; ++ i){
if(fa[i] == i){
ans = ans * 2 % 998244353;
}
}
printf("%lld\n", ans);
return 0;
}