Submission #705216

#	Time	Username	Problem	Language	Result	Execution time	Memory
705216		rainboy	Homework (CEOI22_homework)	C11	100 / 100	137 ms	123592 KiB

Main

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

#define N	1000000
#define INF	0x3f3f3f3f

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

int ej[N * 2][2], eo[N * 2]; char tt[N * 2];

void append(int i, int j) {
	ej[i][eo[i]++] = j;
}

int ll[N * 2], rr[N * 2], sz[N * 2];

void dfs(int i) {
	int o;

	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j);
		sz[i] += sz[j];
	}
	if (tt[i] == -1)
		ll[i] = rr[i] = 0, sz[i] = 1;
	else if (tt[i] == 0) {
		ll[i] = INF, rr[i] = 0;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			ll[i] = min(ll[i], ll[j]);
			rr[i] += rr[j];
		}
	} else {
		ll[i] = eo[i] - 1, rr[i] = 0;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			ll[i] += ll[j], rr[i] = max(rr[i], sz[i] - sz[j] + rr[j]);
		}
	}
}

int main() {
	static char cc[N * 7];
	static int qu[N * 2];
	int n, n_, cnt, i;

	scanf("%s", cc), n = strlen(cc);
	n_ = 0, cnt = 0;
	for (i = 0; i < n; i++)
		if (cc[i] == 'm') {
			if (cnt)
				append(qu[cnt - 1], n_);
			tt[qu[cnt++] = n_++] = cc[i + 1] == 'i' ? 0 : 1;
		} else if (cc[i] == '?') {
			append(qu[cnt - 1], n_);
			tt[n_++] = -1;
		} else if (cc[i] == ')')
			cnt--;
	dfs(0);
	printf("%d\n", rr[0] - ll[0] + 1);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%s", cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34