QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547900#7755. Game on a ForestCodeK_GWA 1ms4356kbC++171.4kb2024-09-05 12:42:132024-09-05 12:42:13

Judging History

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

  • [2024-09-05 12:42:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4356kb
  • [2024-09-05 12:42:13]
  • 提交

answer

# include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], tag[N], num[N], sum[N], idx;

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int id)
{
	tag[u] = id;
	int d = 1;
	for(int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		d += dfs(j, id);
	}
	return num[u] = d;
}

int main()
{
	memset(h, -1, sizeof h);
	scanf("%d%d", &n, &m);
	while(m --)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
	}
	
	int id = 0;
	for(int i = 1; i <= n; i ++)
		if(!tag[i])
			dfs(i, ++ id);
	for(int i = 1; i <= n; i ++) sum[tag[i]] ++;
	
	int res = 0, odd = 0, even = 0;
	for(int i = 1; i <= n; i ++)
		if(sum[i])
		{
			if(sum[i] % 2) odd ++;
			else even ++;
		}
		else break;
		
	for(int i = 1; i <= n; i ++)
	{
		int t1 = odd, t2 = even;
		if(sum[tag[i]] % 2) t1 --;
		else t2 --;
		
		for(int j = h[i]; ~j; j = ne[j])
		{
			int u = e[j];
			
			int r1 = t1, r2 = t2;
			if(num[u] % 2) r1 ++;
			else r2 ++;
			
			if((sum[tag[i]] - num[u]) % 2) r1 ++;
			else r2 ++;
			if(r1 % 2 == 0 && r2 % 2 == 0) res ++;
		}
		
		for(int j = h[i]; ~j; j = ne[j])
		{
			int u = e[j];
			if(num[u] % 2) t1 ++;
			else t2 ++;
		}
		if(sum[tag[i]] > 1)
		{
			if((sum[tag[i]] - num[i]) % 2) t1 ++;
			else t2 ++;
		}
		if(t1 % 2 == 0 && t2 % 2 == 0) res ++;
	}
	printf("%d\n", res);
	return 0;
}
	
	
	

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4356kb

input:

3 1
1 2

output:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'