QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#264448#7755. Game on a Forestqyh619718WA 4ms11832kbC++142.0kb2023-11-25 14:03:572023-11-25 14:03:58

Judging History

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

  • [2023-11-25 14:03:58]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:11832kb
  • [2023-11-25 14:03:57]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ff ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5+7;

vector<int>vec[N];
int root;
vector<int>vec_root;
int vis[N] , depth[N];
int mp1[N] , mp2[N] , mp3[N];
int root_tp[N];
pair<int , int>pp[N];
void dfs(int tp , int p , int deep)
{
	vis[p]=1;
	depth[p]=deep;
	root_tp[p]=tp;
	int sz=vec[p].size();
	if(sz==1&&p!=root)
	{
		mp1[p]=1;
		mp2[p]=0;
		mp3[p]=0;
		return;
	}
	for(int i=0;i<sz;i++)
	{
		if(vis[vec[p][i]]==1) continue;
		dfs(tp , vec[p][i]  , deep+1);
		if(mp1[vec[p][i]]&1) mp2[p]++;
		else mp3[p]++;
		mp1[p]+=mp1[vec[p][i]]+1; 
	}
}
signed main()
{
	int n , m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u , v;
		cin>>u>>v;
		pp[i]={u , v};
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int odd=0 , even=0;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			root=i;
			vec_root.push_back(i);
			dfs(i , root , 0);
			if(mp1[i]==0) mp1[i]=1;
			if(mp1[i]&1) odd++;
			else even++;
		}
	}
//	cout<<odd<<" "<<even<<endl;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int oddd=odd , evenn=even;
		if(mp1[root_tp[i]]&1) oddd--;
		else evenn--;
		if((mp1[root_tp[i]]-mp1[i])&1) oddd++;
		else  evenn++;
		oddd+=mp2[i];
		evenn+=mp3[i];
		if((oddd%2==0)&&(evenn%2==0)) ans++;
	}
//	for(int i=1;i<=n;i++) cout<<mp1[i]<<" "<<mp2[i]<<" "<<mp3[i]<<endl;
//	for(int i=1;i<=n;i++) cout<<depth[i]<<endl;
	for(int i=1;i<=m;i++)
	{
		int oddd=odd , evenn=even;
		if(mp1[root_tp[pp[i].first]]&1) oddd--;
		else evenn--;		
		if(depth[pp[i].first]>depth[pp[i].second])
		{
			if((mp1[root_tp[pp[i].first]]-mp1[pp[i].first])&1)oddd++;
			else evenn++;
			if(mp1[pp[i].first]&1) oddd++;
			else evenn++;
		}
		else
		{
			if((mp1[root_tp[pp[i].second]]-mp1[pp[i].second])&1)oddd++;
			else evenn++;
			if(mp1[pp[i].second]&1) oddd++;
			else evenn++;
		}
		if((oddd%2==0)&&(evenn%2==0)) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10832kb

input:

3 1
1 2

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11832kb

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: 10748kb

input:

100000 1
4647 17816

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9436kb

input:

100000 2
64075 72287
63658 66936

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 10960kb

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: 9340kb

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: 11776kb

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'