제출 #1353025

#제출 시각아이디문제언어결과실행 시간메모리
1353025raineyjHomework (CEOI22_homework)C++20
100 / 100
176 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;
        if(c[v].size()==2) val[v][(t[v]+1)%2]=min(val[c[v][0]][(t[v]+1)%2], val[c[v][1]][(t[v]+1)%2]);
        for(auto child : c[v])
        {
            val[v][t[v]]+=val[child][t[v]];
        }
        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...