QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649029#7755. Game on a ForestqkyWA 2ms7048kbC++171.6kb2024-10-17 21:20:382024-10-17 21:20:40

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 21:20:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7048kb
  • [2024-10-17 21:20:38]
  • 提交

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'