제출 #544758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544758		rainboy	Inside information (BOI21_servers)	C11	100 / 100	402 ms	48472 KiB

servers

/* upsolve using centroid decomposition */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N	120000
#define LN	16	/* LN = floor(log2(N)) */
#define Q	240000
 
int min(int a, int b) { return a < b ? a : b; }
 
int uu[N - 1], vv[N - 1], m;
 
int *eh[N], eo[N];
 
void append(int i, int h) {
	int o = eo[i]++;
 
	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}
 
int cc[N][LN], xx[N][LN], kk[N], *ft[N]; char bb[N][LN];
int sz[N], c_;
 
void dfs(int f, int i, int n, int k, int c, int x, int up, int dn) {
	int o, centroid;
 
	if (k >= 0)
		cc[i][k] = c, xx[i][k] = x, bb[i][k] = up | dn << 1, kk[i]++;
	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ uu[h] ^ vv[h];

		if (h != f) {
			dfs(h, j, n, k, c, x, up && f > h, dn && f < h);
			if (sz[j] * 2 > n)
				centroid = 0;
			sz[i] += sz[j];
		}
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		c_ = i;
}
 
void delete_(int i, int h) {
	int o;

	for (o = eo[i]; o--; )
		if (eh[i][o] == h) {
			eo[i]--;
			while (o < eo[i])
				eh[i][o] = eh[i][o + 1], o++;
			return;
		}
}

void cd(int f, int x, int i, int n, int k, int c) {
	int o;

	dfs(f, i, n, k, c, x, 1, 1), c = c_;
	ft[c] = (int *) calloc(eo[c], sizeof *ft[c]);
	x = 0;
	for (o = 0; o < eo[c]; o++) {
		int h = eh[c][o], j = c ^ uu[h] ^ vv[h];

		delete_(j, h);
		cd(h, x++, j, sz[j] < sz[c] ? sz[j] : n - sz[c], k + 1, c);
	}
}

int ds[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;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

void update(int *ft, int i, int n) {
	while (i < n) {
		ft[i]++;
		i |= i + 1;
	}
}

int query(int *ft, int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

void update_(int i, int j) {
	int k, i_, j_, c;

	i_ = find(i), j_ = find(j);
	for (k = 0; k < kk[i]; k++) {
		c = cc[i][k];
		if ((bb[i][k] & 2) != 0 && find(c) == j_)
			update(ft[c], eo[c] - 1 - xx[i][k], eo[c]);
	}
	for (k = 0; k < kk[j]; k++) {
		c = cc[j][k];
		if ((bb[j][k] & 2) != 0 && find(c) == i_)
			update(ft[c], eo[c] - 1 - xx[j][k], eo[c]);
	}
	join(i, j);
}

int query_(int i, int j) {
	int k;

	if (i == j)
		return 1;
	if (find(i) != find(j))
		return 0;
	if (kk[i] > kk[j] && cc[i][kk[j]] == j)
		return (bb[i][kk[j]] & 1) != 0;
	if (kk[j] > kk[i] && cc[j][kk[i]] == i)
		return (bb[j][kk[i]] & 2) != 0;
	for (k = min(kk[i], kk[j]) - 1; k >= 0; k--)
		if (cc[i][k] == cc[j][k])
			return (bb[i][k] & 1) != 0 && (bb[j][k] & 2) != 0 && xx[i][k] < xx[j][k];
	return 0;
}

int count(int i) {
	int k, i_, c, ans;

	ans = query(ft[i], eo[i] - 1) + 1, i_ = find(i);
	for (k = 0; k < kk[i]; k++) {
		c = cc[i][k];
		if ((bb[i][k] & 1) != 0 && find(c) == i_)
			ans += query(ft[c], eo[c] - 1 - xx[i][k] - 1) + 1;
	}
	return ans;
}

int main() {
	static char tt[Q];
	static int ii[Q], jj[Q];
	int n, q, h, i;
 
	scanf("%d%d", &n, &q), q += n - 1;
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < q; h++) {
		static char s[2];
 
		scanf("%s", s), tt[h] = s[0];
		if (tt[h] == 'C')
			scanf("%d", &ii[h]), ii[h]--;
		else {
			scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
			if (tt[h] == 'S')
				uu[m] = ii[h], vv[m] = jj[h], append(ii[h], m), append(jj[h], m), m++;
		}
	}
	cd(-1, -1, 0, n, -1, -1);
	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < q; h++)
		if (tt[h] == 'S')
			update_(ii[h], jj[h]);
		else if (tt[h] == 'Q')
			printf(query_(jj[h], ii[h]) ? "yes\n" : "no\n");
		else
			printf("%d\n", count(ii[h]));
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.c: In function 'append':
servers.c:19:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   19 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
servers.c: In function 'main':
servers.c:163:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |  scanf("%d%d", &n, &q), q += n - 1;
      |  ^~~~~~~~~~~~~~~~~~~~~
servers.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |   scanf("%s", s), tt[h] = s[0];
      |   ^~~~~~~~~~~~~~
servers.c:171:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |    scanf("%d", &ii[h]), ii[h]--;
      |    ^~~~~~~~~~~~~~~~~~~
servers.c:173:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |    scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5