Submission #722790

#	Time	Username	Problem	Language	Result	Execution time	Memory
722790		rainboy	Marshmallow Molecules (CCO19_day2problem2)	C11	25 / 25	230 ms	16124 KiB

Main

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

#define N	100000
#define M	100000
#define MD	0x7fffffff

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int X = 123454321;

int hash(int u, int v) {
	return ((long long) u * X + v) % MD % M;
}

int *eu[M], *ev[M], eo_[M];

void init() {
	int h;

	for (h = 0; h < M; h++) {
		eu[h] = (int *) malloc(2 * sizeof *eu[h]);
		ev[h] = (int *) malloc(2 * sizeof *ev[h]);
	}
}

void add(int u, int v) {
	int h = hash(u, v), o = eo_[h]++;

	if (o >= 2 && (o & o - 1) == 0) {
		eu[h] = (int *) realloc(eu[h], o * 2 * sizeof *eu[h]);
		ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
	}
	eu[h][o] = u, ev[h][o] = v;
}

void remove_(int u, int v) {
	int h = hash(u, v), o;

	for (o = eo_[h]; o--; )
		if (eu[h][o] == u && ev[h][o] == v) {
			eo_[h]--;
			while (o < eo_[h])
				eu[h][o] = eu[h][o + 1], ev[h][o] = ev[h][o + 1], o++;
			return;
		}
}

int contains(int u, int v) {
	int h = hash(u, v), o;

	for (o = eo_[h]; o--; )
		if (eu[h][o] == u && ev[h][o] == v)
			return 1;
	return 0;
}

int ds[N];

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

int dd[N];

void merge(int i, int j) {
	int o;

	if (contains(i, j))
		remove_(i, j), remove_(j, i), dd[i]--, dd[j]--;
	for (o = eo[i]; o--; ) {
		int k = find(ej[i][o]);

		if (!contains(i, k))
			continue;
		append(j, k);
		remove_(i, k), remove_(k, i), dd[i]--, dd[k]--;
		if (!contains(j, k))
			add(j, k), add(k, j), dd[j]++, dd[k]++;
	}
	free(ej[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, merge(i, j);
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, merge(j, i);
	}
}

int main() {
	static int ii[N];
	int n, m, cnt, h, i, j, o;
	long long ans;

	init();
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
		add(i, j), add(j, i), dd[i]++, dd[j]++;
	}
	memset(ds, -1, n * sizeof *ds);
	ans = 0;
	for (j = 0; j < n; j++) {
		cnt = 0;
		for (o = eo[j]; o--; ) {
			i = ej[j][o];
			if (i < j)
				ii[cnt++] = i;
		}
		while (cnt--)
			join(ii[cnt], j);
		ans += dd[find(j)];
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'add':
Main.c:39:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Main.c: In function 'main':
Main.c:113:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:117:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10