Submission #766591

#	Time	Username	Problem	Language	Result	Execution time	Memory
766591		Pichon5	Homework (CEOI22_homework)	C++17	100 / 100	309 ms	135772 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define pb push_back
#define F first
#define S second
#define vi vector<int>
#define ll long long
#define int long long
#define fore for(int i = 0; i < n; i++)
using namespace std;
const int tam=2000005;
vi G[tam];
int color[tam];

int fmin(int nodo){
    if(G[nodo].size()==0)return 1;
    if(color[nodo]){
        int sum=0;
        for(auto it : G[nodo]){
            sum+=fmin(it);
        }
        return sum;
    }else{
        int mi=1e9;
        for(auto it : G[nodo]){
            mi=min(fmin(it),mi);
        }
        return mi;
    }
}

int fmax(int nodo){
    if(G[nodo].size()==0)return 1;
    if(color[nodo]==0){
        // cout<<"coloreado"<<endl;
        int sum=0;
        for(auto it : G[nodo]){
            sum+=fmax(it);
        }
        return sum;
    }else{
        int mi=1e9;
        for(auto it : G[nodo]){
            mi=min(fmax(it),mi);
        }
        return mi;
    }
}
signed main()
{
    string s;
    cin >> s;
    int n = s.size();
    stack<int>nodos;
    int nodo=1;
    int leaves=0;
    for(int i=0;i<n;i++){
        if(s[i]=='x'){
            nodos.push(nodo);
            color[nodo]=1;
            nodo++;
            continue;
        }
        if(s[i]=='n'){
            nodos.push(nodo);
            nodo++;
            continue;
        }
        if(s[i]=='?'){
            leaves++;
            int padre=nodos.top();
            G[padre].pb(nodo);
            nodo++;
        }
        if(s[i]==')'){
            int quito=nodos.top();
            nodos.pop();
            if(nodos.empty())continue;
            int padre=nodos.top();
            G[padre].pb(quito);
        }
    }
    //wanna print the graph
    for(int i=1;i<=n;i++){
        //cout<<i<<" : ";
        for(auto it : G[i]){
            // cout<<i<<" "<<it<<endl;
        }
    }
        // cout<<endl;
    int mi=fmin(1);
    // cout<<"mi  "<<mi<<endl;
    // for(int i=1;i<=n;i++){
    //     cout<<i<<" "<<color[i]<<endl;
    //     color[i]=!color[i];
    // }
    int ma=fmax(1);
    ma=leaves-ma+1;
    cout<<ma-mi+1<<endl;
    
    return 0;
}  

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:100:18: warning: unused variable 'it' [-Wunused-variable]
  100 |         for(auto it : G[i]){
      |                  ^~

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