Submission #487031

#	Time	Username	Problem	Language	Result	Execution time	Memory
487031		rainboy	Zagrade (COI17_zagrade)	C11	100 / 100	674 ms	45988 KiB

zagrade

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

#define N	300000

int max(int a, int b) { return a > b ? a : b; }

int *ej[N], eo[N]; char cc[N + 1];

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 sz[N], c;

void dfs0(int p, int i, int n) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs0(i, j, n);
			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 j) {
	int o;

	for (o = eo[i]; o--; )
		if (ej[i][o] == j) {
			eo[i]--;
			while (o < eo[i])
				ej[i][o] = ej[i][o + 1], o++;
		}
}

long long ans;

int kk[N + 1], ll[N + 1], dd1[N], dd2[N], cnt1, cnt2;

void dfs1(int p, int i, int d, int d_) {
	int o;

	if (cc[i] == '(')
		d_ = max(d_, ++d);
	else
		d--;
	if (d == d_)
		ans += ll[d], dd1[cnt1++] = d;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs1(i, j, d, d_);
	}
}

void dfs2(int p, int i, int d, int d_) {
	int o;

	if (cc[i] == ')')
		d_ = max(d_, ++d);
	else
		d--;
	if (d == d_)
		ans += kk[d], dd2[cnt2++] = d;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j, d, d_);
	}
}

void cd(int i, int n) {
	int o;

	dfs0(-1, i, n), i = c;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		delete(j, i);
	}
	memset(kk, 0, (n + 1) * sizeof *kk), memset(ll, 0, (n + 1) * sizeof *ll), kk[0] = 1;
	if (cc[i] == ')')
		ll[1] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		cnt1 = cnt2 = 0;
		dfs1(i, j, 0, 0), dfs2(i, j, cc[i] == ')' ? 1 : -1, cc[i] == ')' ? 1 : 0);
		while (cnt1--)
			kk[dd1[cnt1]]++;
		while (cnt2--)
			ll[dd2[cnt2]]++;
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]);
	}
}

int main() {
	int n, h, i, j;

	scanf("%d%s", &n, cc);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	cd(0, n);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60