oj.uz

Submission #487031

# Submission time Handle Problem Language Result Execution time Memory
487031 2021-11-13T20:29:22 Z rainboy Zagrade (COI17_zagrade) C
100 / 100
 674 ms 45988 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 44668 KB Output is correct
2 Correct 287 ms 44992 KB Output is correct
3 Correct 303 ms 44676 KB Output is correct
4 Correct 275 ms 44940 KB Output is correct
5 Correct 294 ms 44668 KB Output is correct
6 Correct 291 ms 44812 KB Output is correct
7 Correct 291 ms 44732 KB Output is correct
8 Correct 303 ms 44816 KB Output is correct
9 Correct 287 ms 44680 KB Output is correct
10 Correct 265 ms 45840 KB Output is correct
11 Correct 254 ms 45140 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 293 ms 44668 KB Output is correct
12 Correct 287 ms 44992 KB Output is correct
13 Correct 303 ms 44676 KB Output is correct
14 Correct 275 ms 44940 KB Output is correct
15 Correct 294 ms 44668 KB Output is correct
16 Correct 291 ms 44812 KB Output is correct
17 Correct 291 ms 44732 KB Output is correct
18 Correct 303 ms 44816 KB Output is correct
19 Correct 287 ms 44680 KB Output is correct
20 Correct 265 ms 45840 KB Output is correct
21 Correct 254 ms 45140 KB Output is correct
22 Correct 547 ms 22012 KB Output is correct
23 Correct 674 ms 22004 KB Output is correct
24 Correct 545 ms 21904 KB Output is correct
25 Correct 587 ms 22012 KB Output is correct
26 Correct 346 ms 29124 KB Output is correct
27 Correct 351 ms 25672 KB Output is correct
28 Correct 347 ms 24316 KB Output is correct
29 Correct 247 ms 45836 KB Output is correct
30 Correct 258 ms 45988 KB Output is correct
31 Correct 99 ms 21588 KB Output is correct
32 Correct 249 ms 45256 KB Output is correct