Submission #968643

#	Time	Username	Problem	Language	Result	Execution time	Memory
968643		tset	Homework (CEOI22_homework)	C++14	100 / 100	400 ms	151204 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int INF = 1e18 +42;

struct Noeud
{
    int type, l, r;
};

vector<Noeud> noeuds;
int N = 0;

pii getAns(int nde)
{
    if(noeuds[nde].type == 0)
        return {1, 1};
    pii ansLeft = getAns(noeuds[nde].l);
    pii ansRight = getAns(noeuds[nde].r);
    if(noeuds[nde].type == 1)
        return {ansLeft.first + ansRight.first, min(ansLeft.second, ansRight.second)};
    return {min(ansLeft.first, ansRight.first), ansLeft.second + ansRight.second};
}


int parse()
{
    char car, useless;
    cin >> car;
    if(car == '?')
    {
        int id = noeuds.size();
        noeuds.push_back({0, -1, -1});
        N++;
        return id;        
    }
    cin >> car;
    cin >> car;
    cin >> useless;
    int l = parse();
    cin >> useless;
    int r = parse();
    cin >> useless;
    int id = noeuds.size();
    if(car == 'x')
        noeuds.push_back({1, l, r});
    else
        noeuds.push_back({-1, l, r});
    return id;
}

signed main()
{
    int rootNode = parse();
    pii ans = getAns(rootNode);
    cout << max(1ll, N - ans.first - ans.second +2) << endl;
}

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