Submission #972479

#TimeUsernameProblemLanguageResultExecution timeMemory
972479vjudge1Homework (CEOI22_homework)C11
100 / 100
109 ms98652 KiB
#include <stdio.h> #define N 3000005 int a[N], b[N], l[N], r[N], alc, sz[N], type[N]; int read() { char c; int p = ++alc; c = getchar(); if (c == '?') { l[p] = r[p] = 0; a[p] = b[p] = 0; sz[p] = 1; type[p] = 0; return p; } c = getchar(); c = getchar(); getchar(); l[p] = read(); getchar(); r[p] = read(); getchar(); sz[p]=sz[l[p]]+sz[r[p]]; type[p] = 1 + (c == 'x'); return p; } int dfs(int v) { if(type[v]==0)return 1; dfs(l[v]),dfs(r[v]); if(type[v]==1) { a[v]=a[l[v]]<a[r[v]]?a[l[v]]:a[r[v]]; b[v]=b[l[v]]+b[r[v]]+1; } else { a[v]=a[l[v]]+a[r[v]]+1; b[v]=b[l[v]]<b[r[v]]?b[l[v]]:b[r[v]]; } return sz[v]-a[v]-b[v]; } int main() { printf("%d", dfs(read())); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...