Submission #74235231

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
int *ec, **es;
void ae(int f, int t) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = t;
}
int *mincost;
int main(void) {
  int n, m;
  int i;
  int *q, qs = 0, qe = 0;
  int ans = 0;
  if (scanf("%d%d", &n, &m) != 2) return 1;
  ec = calloc(n + 1, sizeof(*ec));
  es = calloc(n + 1 ,sizeof(*es));
  mincost = malloc(sizeof(*mincost) * (n + 1));
  q = malloc(sizeof(*q) * (n + 1));
  if (ec == NULL || es == NULL || mincost == NULL || q == NULL) return 2;
  for (i = 1; i <= n; i++) mincost[i] = n + 10;
  for (i = 0; i < m; i++) {
    int a, b;
    if (scanf("%d%d", &a, &b) != 2) return 1;
    ae(a, b);
    ae(b, a);
  }
  mincost[1] = 0;
  q[qe++] = 1;
  while (qs < qe) {
    int cur = q[qs++];
    for (i = 0; i < ec[cur]; i++) {
      int next = es[cur][i];
      if (mincost[next] > mincost[cur] + 1) {
        mincost[next] = mincost[cur] + 1;
        q[qe++] = next;
      }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

int *ec, **es;

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int *mincost;

int main(void) {
	int n, m;
	int i;
	int *q, qs = 0, qe = 0;
	int ans = 0;
	if (scanf("%d%d", &n, &m) != 2) return 1;
	ec = calloc(n + 1, sizeof(*ec));
	es = calloc(n + 1 ,sizeof(*es));
	mincost = malloc(sizeof(*mincost) * (n + 1));
	q = malloc(sizeof(*q) * (n + 1));
	if (ec == NULL || es == NULL || mincost == NULL || q == NULL) return 2;
	for (i = 1; i <= n; i++) mincost[i] = n + 10;
	for (i = 0; i < m; i++) {
		int a, b;
		if (scanf("%d%d", &a, &b) != 2) return 1;
		ae(a, b);
		ae(b, a);
	}
	mincost[1] = 0;
	q[qe++] = 1;
	while (qs < qe) {
		int cur = q[qs++];
		for (i = 0; i < ec[cur]; i++) {
			int next = es[cur][i];
			if (mincost[next] > mincost[cur] + 1) {
				mincost[next] = mincost[cur] + 1;
				q[qe++] = next;
			}
		}
	}
	for (i = 2; i <= n; i++) {
		if (mincost[i] <= 2) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result