Submission #1353012

#TimeUsernameProblemLanguageResultExecution timeMemory
1353012raineyjHomework (CEOI22_homework)C++20
0 / 100
128 ms125040 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string n;
    cin >> n;
    vector<int> p;
    vector<vector<int>> c;
    vector<int> t;
    stack<int> curp;
    int node=0, count=0;
    curp.push(0);
    p.push_back(0);
    c.push_back(vector<int>(0));
    if(n[2]=='x') t.push_back(0);
    else t.push_back(1);
    for(int i=3; i<n.size(); i++)
    {
        if(n[i]==')') curp.pop();
        else if(n[i]=='x')
        {
            node++;
            p.push_back(curp.top());
            c.push_back(vector<int>(0));
            c[curp.top()].push_back(node);
            t.push_back(0);
            curp.push(node);
        }
        else if(n[i]=='n')
        {
            node++;
            p.push_back(curp.top());
            c.push_back(vector<int>(0));
            c[curp.top()].push_back(node);
            t.push_back(1);
            curp.push(node);
        }
        else if(n[i]=='?') count++;
    }
    queue<int> q;
    for(int i=0; i<=node; i++)
    {
        if(c[i].size()==0) q.push(i);
    }
    vector<bool> seen(node+1, false);
    vector<vector<int>> val(node+1, vector<int>(2, 0));
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        if(seen[v]) continue;
        bool sc=true;
        for(auto child : c[v])
        {
            if(!seen[child]) sc=false;
        }
        if(!sc) continue;
        val[v][t[v]]+=1;
        for(auto child : c[v])
        {
            val[v][0]+=val[child][0];
            val[v][1]+=val[child][1];
        }
        val[v][(t[v]+1)%2]=max(0, val[v][(t[v]+1)%2]-1);
        seen[v]=true;
        if(p[v]!=v) q.push(p[v]);
    }
    cout << count-(val[0][0]+val[0][1]) << '\n';
}
#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...