Submission #536322

#	Time	Username	Problem	Language	Result	Execution time	Memory
536322		rainboy	우호 조약 체결 (JOI14_friends)	C11	35 / 100	243 ms	26868 KiB

friends

#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 (stderr)

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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65