Submission #917347

#	Time	Username	Problem	Language	Result	Execution time	Memory
917347		rainboy	산만한 고양이 (KOI17_cat)	C++17	100 / 100	254 ms	43068 KiB

cat

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

#define N	300000
#define j1	J1	/* hahaha */

int n, m;
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 pp[N], dd[N], i1, j1, i2, j2;

void dfs(int p, int i, int d) {
	int o;

	pp[i] = p, dd[i] = d++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			if (!dd[j])
				dfs(i, j, d + 1);
			else if (dd[i] < dd[j]) {
				if (i1 == -1 && j1 == -1)
					i1 = i, j1 = j;
				else
					i2 = i, j2 = j;
			}
		}
	}
}

int lca(int i, int j) {
	while (i != j)
		if (dd[i] > dd[j])
			i = pp[i];
		else
			j = pp[j];
	return i;
}

int ds[N];

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

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

int check(int i_) {
	int i, j, o;

	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		if (i != i_)
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				if (j != i_ && i < j && !join(i, j))
					return 0;
			}
	return 1;
}

int main() {
	int h, i, j;
	long long ans;

	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);
	}
	i1 = j1 = i2 = j2 = -1, dfs(-1, 0, 1);
	if (i2 == -1 && j2 == -1) {
		ans = 0;
		for (i = j1; i != i1; i = pp[i])
			ans += i + 1;
		ans += i1 + 1;
	} else {
		i = dd[i1] > dd[i2] ? i1 : i2, j = lca(j1, j2);
		ans = 0;
		if (check(i))
			ans += i + 1;
		if (j != i && check(j))
			ans += j + 1;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cat.cpp: In function 'void append(int, int)':
cat.cpp:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
cat.cpp: In function 'int main()':
cat.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
cat.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d%d", &i, &j), i--, j--;
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 55 / 55