Untitled
unknown
c_cpp
2 years ago
2.9 kB
5
Indexable
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 2000000 typedef struct node{ int value; // This is the value of the subtree, not the ID number int tokentype; struct node *leftchild; struct node *rightchild; struct node *parent; //pointing to the parent node }Node; Node* variable[100001]; char s[MAX]; int pos = 0; Node* makeNode(){ Node* nd = (Node*)malloc(sizeof(Node)); int i = pos, num = 0; while(s[i] != ']') i++; for(int j = pos; j < i; j++) num = num*10 + s[j] - '0'; variable[num] = nd; pos = i; nd->value = 0; nd->tokentype = 0; //是變數的話 tokentype = 0 nd->leftchild = NULL, nd->rightchild = NULL, nd->parent = NULL; return nd; } Node* makeOper(){ Node* nd = (Node*)malloc(sizeof(Node)); nd->rightchild = NULL, nd->leftchild = NULL, nd->parent = NULL; nd->value = 0; if(s[pos] == '|') nd->tokentype = 1; // 是or的話 tokentype = 1 else if(s[pos] == '&') nd->tokentype = 2; // 是and的話 tokentype = 2 return nd; } void freeTree(Node* head){ if(head != NULL){ freeTree(head->leftchild); freeTree(head->rightchild); free(head); } return; } Node* createTree(){ Node* nd = NULL; if(pos < strlen(s)){ if(s[pos] == '|' || s[pos] == '&'){ nd = makeOper(); pos++; nd->leftchild = createTree(); nd->leftchild->parent = nd; pos++; nd->rightchild = createTree(); nd->rightchild->parent = nd; } else if(s[pos] == '['){ pos++; nd = makeNode(); } return nd; } return nd; } void flip(int n){ Node* nd = variable[n]; if(nd->value == 1) nd->value = 0; else nd->value = 1; } void check(Node* nd){ if(nd->parent == NULL) return; Node* pa = nd->parent; int changed = pa->value; if(pa->tokentype == 1){ if(pa->leftchild->value == 1 || pa->rightchild->value == 1) pa->value = 1; else pa->value = 0; } else if(pa->tokentype == 2){ if(pa->leftchild->value == 1 && pa->rightchild->value == 1) pa->value = 1; else pa->value = 0; } if(changed != pa->value) check(pa); return; } int main(){ int t; scanf("%d", &t); while(t--){ int n, m; pos = 0; memset(s, '\0', sizeof(s)); scanf("%d%d%s", &n, &m, s); Node* head = createTree(); for(int i = 0; i < m; i++){ int f; scanf("%d", &f); flip(f); check(variable[f]); printf("%d\n", head->value); } freeTree(head); } }
Editor is loading...