oj.uz

Submission #536322

# Submission time Handle Problem Language Result Execution time Memory
536322 2022-03-12T21:42:55 Z rainboy 우호 조약 체결 (JOI14_friends) C
35 / 100
 243 ms 26868 KB 
#include <stdio.h>
#include <string.h>

#define N	5000

int n;

char adj[N][N];

int ds[N], sz[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, sz[j] += sz[i];
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, sz[i] += sz[j];
	}
}

char visited[N];

void dfs(int i) {
	int j;

	if (visited[i])
		return;
	visited[i] = 1;
	for (j = 0; j < n; j++)
		if (adj[i][j]) {
			join(i, j);
			dfs(j);
		}
}

int main() {
	static int dd[N];
	int m, i, j, j_, ans;

	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		adj[i][j] = 1;
	}
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		sz[i] = 1;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			if (adj[i][j])
				dd[i]++;
		if (dd[i] >= 2) {
			for (j = 0, j_ = -1; j < n; j++)
				if (adj[i][j]) {
					if (j_ == -1)
						j_ = j;
					else
						join(j_, j);
				}
			for (j = 0; j < n; j++)
				if (adj[i][j])
					dfs(j);
		}
	}
	ans = 0;
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			ans += sz[i] == 1 ? dd[i] : sz[i] * (sz[i] - 1);
	printf("%d\n", ans);
	return 0;
}

Compilation message

friends.c: In function 'main':
friends.c:49:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
friends.c:51:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 0 ms 596 KB Output is correct
12 Correct 0 ms 596 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 0 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13832 KB Output is correct
2 Correct 33 ms 7264 KB Output is correct
3 Correct 177 ms 24144 KB Output is correct
4 Correct 220 ms 26256 KB Output is correct
5 Correct 210 ms 26028 KB Output is correct
6 Correct 243 ms 26868 KB Output is correct
7 Correct 8 ms 3924 KB Output is correct
8 Correct 13 ms 4616 KB Output is correct
9 Correct 18 ms 5044 KB Output is correct
10 Correct 202 ms 25492 KB Output is correct
11 Correct 239 ms 26828 KB Output is correct
12 Correct 168 ms 23508 KB Output is correct
13 Correct 77 ms 14988 KB Output is correct
14 Correct 58 ms 10536 KB Output is correct
15 Correct 100 ms 16596 KB Output is correct
16 Correct 151 ms 22616 KB Output is correct
17 Correct 234 ms 26744 KB Output is correct
18 Correct 26 ms 20436 KB Output is correct
19 Correct 44 ms 20636 KB Output is correct
20 Correct 240 ms 26828 KB Output is correct
21 Correct 70 ms 15352 KB Output is correct
22 Correct 73 ms 15492 KB Output is correct
23 Correct 132 ms 20852 KB Output is correct
24 Correct 75 ms 11260 KB Output is correct
25 Correct 27 ms 19684 KB Output is correct
26 Correct 65 ms 14432 KB Output is correct
27 Correct 27 ms 20428 KB Output is correct
28 Correct 71 ms 15480 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 11800 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -