oj.uz

답안 #670398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670398 2022-12-08T21:45:28 Z rainboy 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C
0 / 100
 27 ms 35840 KB 
#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 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);
		} else {
			int r = find(k - n);

			if (r == j || r == i)
				continue;
			if (get(k, i)) {
				remove_(k, i);
				if (get(k, j))
					add(r, 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

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:118:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
joitter2.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 35484 KB Output is correct
2 Correct 25 ms 35524 KB Output is correct
3 Correct 27 ms 35524 KB Output is correct
4 Correct 26 ms 35464 KB Output is correct
5 Correct 27 ms 35608 KB Output is correct
6 Correct 27 ms 35532 KB Output is correct
7 Correct 27 ms 35840 KB Output is correct
8 Incorrect 27 ms 35836 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 35484 KB Output is correct
2 Correct 25 ms 35524 KB Output is correct
3 Correct 27 ms 35524 KB Output is correct
4 Correct 26 ms 35464 KB Output is correct
5 Correct 27 ms 35608 KB Output is correct
6 Correct 27 ms 35532 KB Output is correct
7 Correct 27 ms 35840 KB Output is correct
8 Incorrect 27 ms 35836 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 35484 KB Output is correct
2 Correct 25 ms 35524 KB Output is correct
3 Correct 27 ms 35524 KB Output is correct
4 Correct 26 ms 35464 KB Output is correct
5 Correct 27 ms 35608 KB Output is correct
6 Correct 27 ms 35532 KB Output is correct
7 Correct 27 ms 35840 KB Output is correct
8 Incorrect 27 ms 35836 KB Output isn't correct
9 Halted 0 ms 0 KB -