QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #282705 | #7313. Connected Spanning Subgraph | ChrysanthBlossom | WA | 20ms | 3684kb | C++14 | 652b | 2023-12-12 20:04:42 | 2023-12-12 20:04:43 |
Judging History
answer
#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn=1e6+7;
// 18:34-18:52
int f[maxn];
int n;
int find(int k){
return (f[k]==k?k:f[k]=find(f[k]));
}
void init(){
for(ri i=1;i<=n<<1;i++)f[i]=i;
}
bool mrg(int a,int b){
a=find(a);b=find(b);
if(a==b)return 1;
f[a]=b;return 0;
}
bool merge(int a,int b){
if(mrg(a,b+n)||mrg(a+n,b))return 1;
return 0;
}
int m;
signed main(){
ios::sync_with_stdio(0);
while(cin>>n>>m){
init();
bool f=1;
for(ri i=1;i<=m;i++){
int u,v;cin>>u>>v;
if(merge(u,v)){
f=0;
}
}
cout<<f<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
2 1 1 2 3 2 1 2 2 3 3 3 1 2 2 3 3 1
output:
1 1 0
result:
ok 3 number(s): "1 1 0"
Test #2:
score: -100
Wrong Answer
time: 20ms
memory: 3684kb
input:
11 14 7 5 2 6 10 3 8 2 8 11 4 6 11 1 5 6 1 10 5 4 5 2 4 3 1 7 8 9 4 4 1 4 2 4 2 3 3 4 10 18 9 10 1 8 10 6 3 5 4 10 10 8 3 1 2 6 4 2 8 2 3 2 5 9 6 5 5 4 8 7 9 7 10 3 1 4 3 2 3 1 2 1 15 27 10 2 3 12 12 6 8 4 5 8 6 9 9 7 4 9 1 6 3 14 13 8 2 12 2 6 8 11 4 11 14 1 15 5 13 11 1 12 15 2 11 15 12 11 15 14 8...
output:
0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 ...
result:
wrong answer 3rd numbers differ - expected: '1', found: '0'