제출 #972486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972486		sleepntsheep	Homework (CEOI22_homework)	C11	100 / 100	100 ms	94548 KiB

Main

#include <stdio.h>

#define N 2000005

int a[N], b[N], l[N], r[N], alc, sz[N], type[N];

int read()
{
    int c, p = ++alc;
    c = getchar();
    if (c == '?')
    {
        l[p] = r[p] = 0;
        a[p] = b[p] = 0;
        sz[p] = 1;
        type[p] = 0;
        return p;
    }
    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())); }

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