Submission #670405

#	Time	Username	Problem	Language	Result	Execution time	Memory
670405		rainboy	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C11	100 / 100	856 ms	56248 KiB

joitter2

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

#define N	100000
#define M	300000
#define X	0x3f3f3f3f
#define MD	0x7fffffff

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

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

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

	for (o = eo_[h]; o--; )
		if (eu[h][o] == u && ev[h][o] == v) {
			ew[h][o] += w;
			return;
		}
	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]);
		ew[h] = (int *) realloc(ew[h], o * 2 * sizeof *ew[h]);
	}
	eu[h][o] = u, ev[h][o] = v, ew[h][o] = w;
}

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], ew[h][o] = ew[h][o + 1], o++;
			return;
		}
}

int get(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 ew[h][o];
	return 0;
}

int ds[N], sz[N], in[N], *ej[N], eo[N], n;
int uu[M], vv[M], cnt;
long long ans;

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 find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	int o, tmp, d, w;

	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (sz[i] > sz[j])
		tmp = i, i = j, j = tmp;
	if ((w = get(i, j)))
		remove_(i, j), in[j] -= w, ans -= (long long) w * sz[j];
	if ((w = get(j, i)))
		remove_(j, i), in[i] -= w, ans -= (long long) w * sz[i];
	d = in[i] + in[j];
	for (o = eo[i]; o--; ) {
		int k = ej[i][o];

		if (k < n) {
			int k_ = find(k), wik = get(i, k_), wki = get(k_, i), wjk = get(j, k_), wkj = get(k_, j);

			remove_(i, k_), remove_(k_, i);
			if (wik && wkj || wki && wjk)
				uu[cnt] = j, vv[cnt] = k_, cnt++;
			add(j, k_, wik), add(k_, j, wki);
			append(j, k_);
		}
	}
	for (o = eo[i]; o--; ) {
		int k = ej[i][o];

		if (k >= n) {
			int k_ = find(k - n);

			if (k_ == j || k_ == i)
				continue;
			if (get(k, i)) {
				remove_(k, i);
				if (get(k, j))
					add(k_, j, -1), d--;
				else
					add(k, j, 1);
				append(j, k);
			}
		}
	}
	free(ej[i]);
	ans -= (long long) in[i] * sz[i] + (long long) in[j] * sz[j];
	ans += (long long) sz[i] * sz[j] * 2;
	ds[i] = j, sz[j] += sz[i], in[j] = d;
	ans += (long long) in[j] * sz[j];
}

int main() {
	int m, h, i, j, u, v;

	scanf("%d%d", &n, &m);
	for (h = 0; h < M; h++) {
		eu[h] = (int *) malloc(2 * sizeof *eu[h]);
		ev[h] = (int *) malloc(2 * sizeof *ev[h]);
		ew[h] = (int *) malloc(2 * sizeof *ew[h]);
	}
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ds[i] = -1, sz[i] = 1;
	}
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		u = find(i), v = find(j);
		if (u != v) {
			if (!get(n + i, v))
				in[v]++, ans += sz[v], add(n + i, v, 1), add(u, v, 1), append(v, n + i);
			append(u, v), append(v, u);
			if (get(v, u)) {
				cnt = 0;
				uu[cnt] = i, vv[cnt] = j, cnt++;
				while (cnt)
					cnt--, join(uu[cnt], vv[cnt]);
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

joitter2.c: In function 'add':
joitter2.c:24:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
joitter2.c: In function 'append':
joitter2.c:60:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   60 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
joitter2.c: In function 'join':
joitter2.c:90:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |    if (wik && wkj || wki && wjk)
      |        ~~~~^~~~~~
joitter2.c: In function 'main':
joitter2.c:124:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
joitter2.c:135:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83