QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649029 | #7755. Game on a Forest | qky | WA | 2ms | 7048kb | C++17 | 1.6kb | 2024-10-17 21:20:38 | 2024-10-17 21:20:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int> e[N];
bool vis[N];
int fe[N],sum[N];
int ans;
int df(int u){
vis[u]=1;
int res=1;
for(auto v:e[u]){
if(vis[v]) continue;
res+=df(v);
}
return res;
}
int dfs(int u){
vis[u]=1;
int res=1;
for(auto v:e[u]){
if(vis[v]) continue;
res+=dfs(v);
}
vis[u]=0;
return res;
}
void dfs1(int u,int s){
vis[u]=1;
int sg=s;
for(auto v:e[u]){
sg^=dfs(v)%2==0?2:1;
}
if(sg==0){
ans++;
}
vis[u]=0;
}
bool vvis[N];
void ddfs(int u,int s){
vvis[u]=1;
dfs1(u,s);
for(auto v:e[u]){
if(vvis[v]) continue;
ddfs(v,s);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
int cnt=0;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
fe[++cnt]=i;
sum[cnt]=df(i);
//cout<<"sum["<<cnt<<"]="<<sum[cnt]<<endl;
}
int sg=0;
for(int i=1;i<=cnt;i++){
sg^=(sum[i]%2==0?2:1);
}
for(int i=1;i<=n;i++)vis[i]=0;
for(int i=1;i<=cnt;i++){
int s=sg^(sum[i]%2==0?2:1);
int _in=fe[i];
//cout<<"_in="<<_in<<endl;
ddfs(_in,s);
if(sum[i]%2==1&&s^3==0)ans+=sum[i]-1;
else if(sum[i]%2==0&&s==0)ans+=sum[i]-1;
}
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6088kb
input:
3 1 1 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5968kb
input:
4 3 1 2 2 3 3 4
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 2ms
memory: 6976kb
input:
100000 1 4647 17816
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 6920kb
input:
100000 2 64075 72287 63658 66936
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 7012kb
input:
100000 3 59930 72281 31689 59132 20469 33165
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 2ms
memory: 7004kb
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: 2ms
memory: 7048kb
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:
202
result:
wrong answer 1st numbers differ - expected: '200', found: '202'