QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #638096 | #7755. Game on a Forest | zzuqy# | WA | 8ms | 29484kb | C++14 | 1.1kb | 2024-10-13 14:54:09 | 2024-10-13 14:54:10 |
Judging History
answer
#include<bits/stdc++.h>
#define N 1000009
using namespace std;
int n,m;
vector<int>to[N];
int sz[N],sum,ans;
bool im[N];
void dfs1(int x,int fa){
sz[x]=1;
for(auto y:to[x]){
if(y==fa)continue;
dfs1(y,x);
sz[x]+=sz[y];
}
}
int calc(int x){
if(x%2==1)return 1;
return 2;
}
void dfs2(int x,int fa,int rt){
if(fa!=0){
if((sum^calc(sz[x])^calc(sz[rt]-sz[x]))==0){
//cout<<x<<" "<<sum<<" "<<sz[x]<<" "<<sz[rt]-sz[x]<<endl;
ans++;
}
}
int tmp=sum^calc(sz[rt]-sz[x]);
for(auto y:to[x]){
if(y==fa)continue;
dfs2(y,x,rt);
tmp^=calc(sz[y]);
}
if(tmp==0)ans++;
//cout<<sum<<" "<<x<<" "<<fa<<" "<<rt<<" "<<ans<<endl;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
to[x].push_back(y);
to[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!sz[i]){
im[i]=1,dfs1(i,0);
sum^=calc(sz[i]);
}
}
for(int i=1;i<=n;i++){
sum^=calc(sz[i]);
if(im[i])dfs2(i,0,i);
sum^=calc(sz[i]);
}
cout<<ans;
return 0;
}
/*
8 6
1 2
2 3
3 4
5 6
6 7
7 8
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 27852kb
input:
3 1 1 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 27272kb
input:
4 3 1 2 2 3 3 4
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 4ms
memory: 28148kb
input:
100000 1 4647 17816
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 29036kb
input:
100000 2 64075 72287 63658 66936
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 8ms
memory: 28424kb
input:
100000 3 59930 72281 31689 59132 20469 33165
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 28808kb
input:
100000 10 20391 78923 27822 80617 21749 25732 12929 79693 42889 52515 59064 99869 29031 41875 4463 17813 13407 42498 19120 20957
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 29484kb
input:
99999 101 34378 94161 67696 83255 24557 25591 11476 58475 5684 38157 33843 35321 9046 24028 14293 77681 587 42098 9402 27228 6999 13980 27118 84005 3622 8353 13545 51621 16998 63647 32912 53178 15206 15815 56517 86335 5563 93770 153 278 11242 41753 75098 76792 1695 22836 25936 33352 2765 6778 19597 ...
output:
99898
result:
wrong answer 1st numbers differ - expected: '200', found: '99898'