Submission #950598

#	Time	Username	Problem	Language	Result	Execution time	Memory
950598		Vladth11	Homework (CEOI22_homework)	C++14	100 / 100	180 ms	164052 KiB

Main

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
 
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
 
const ll NMAX = 2000001;
const ll INF = (1LL << 58);
const ll nrbits = 20;
const ll MOD = 998244353;
 
vector <int> v[NMAX];
int pa[NMAX];
int op[NMAX];
pii sol[NMAX];
int nr;
int sz[NMAX];
 
pii combine(int a, int b, int o){
    if(sol[a].first > sol[a].second){
        return sol[a]; /// daca scorul e -1/0 continui
    }
    if(sol[b].first > sol[b].second){
        return sol[b]; /// daca scorul e -1/0 continui
    }
 
 
    if(o == 1){
        return {sol[a].first + sol[b].first, max(sz[a] + sol[b].second, sz[b] + sol[a].second)};
    }else{
        return {min(sol[a].first, sol[b].first), sol[a].second + sol[b].second - 1};
    }
}
 
void DFS(int node){
    if(!v[node].size()){
        sol[node] = {1, 1};
        sz[node] = 1;
        return;
    }
    DFS(v[node][0]);
    DFS(v[node][1]);
    sz[node] += sz[v[node][0]] + sz[v[node][1]];
    sol[node] = combine(v[node][0], v[node][1], op[node]);
}
 
signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int curent = 1, cnt = 1;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == ','){
            v[curent].push_back(++cnt);
            pa[cnt] = curent;
            curent = cnt;
        }
        if(s[i] == '('){
            v[curent].push_back(++cnt);
            pa[cnt] = curent;
            curent = cnt;
        }
        if(s[i] == ')'){
            curent = pa[curent];
        }
        if(s[i] == '?') {
            nr++;
            curent = pa[curent];
        }
        if(s[i] == 'm'){
            if(s[i + 1] == 'a'){
                op[curent] = 1;
            }
            i += 2;
        }
    }
    DFS(1);
    cout << max(0, sol[1].second - sol[1].first + 1);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~

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