Submission #636978

#	Time	Username	Problem	Language	Result	Execution time	Memory
636978		abeker	Homework (CEOI22_homework)	C11	100 / 100	214 ms	143088 KiB

Main

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000005

typedef struct _Node {
  int dp[2];
  int size, type;
  struct _Node *left, *right;
} Node;

int N;
int can[MAX];
char input[10 * MAX];

Node* parse(char** str) {
  Node* res = malloc(sizeof(Node));
  if (**str == 'm') {
    res -> type = *(*str + 1) == 'a';
    *str += 4;
    res -> left = parse(str);
    *str += 1;
    res -> right = parse(str);
    res -> size = res -> left -> size + res -> right -> size;
  }
  else {
    res -> type = -1;
    res -> size = 1;
  }
  *str += 1;
  return res;
}

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

void dfs_dp(Node* x) {
  if (x -> type == -1) {
    x -> dp[0] = x -> dp[1] = 1;
    return;
  }
  int i;
  dfs_dp(x -> left);
  dfs_dp(x -> right);
  for (i = 0; i < 2; i++) 
    if (x -> type == i)
      x -> dp[i] = min(x -> left -> dp[i], x -> right -> dp[i]);
    else
      x -> dp[i] = x -> left -> dp[i] + x -> right -> dp[i];
}

void dfs_solve(Node* x, int smaller, int larger) {
  if (x -> type == -1) {
    can[smaller + 1]++;
    can[N - larger + 1]--;
    return;
  }
  dfs_solve(x -> left, smaller + (x -> type ? x -> right -> dp[0] : 0), larger + (x -> type ? 0 : x -> right -> dp[1]));
  dfs_solve(x -> right, smaller + (x -> type ? x -> left -> dp[0] : 0), larger + (x -> type ? 0 : x -> left -> dp[1]));
}

int main() {
  scanf("%s", input);
  char* foo = input;
  Node* root = parse(&foo);
  N = root -> size;
  dfs_dp(root);
  dfs_solve(root, 0, 0);
  int i, ans = 0;
  for (i = 1; i <= N; i++) {
    can[i] += can[i - 1];
    ans += !!can[i];
  }
  printf("%d\n", ans);
  return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:63:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%s", input);
      |   ^~~~~~~~~~~~~~~~~~

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