oj.uz

Submission #1036900

# Submission time Handle Problem Language Result Execution time Memory
1036900 2024-07-27T19:20:28 Z HorizonWest Homework (CEOI22_homework) C++17
13 / 100
 177 ms 178676 KB 
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

vector <vector<int>> v;
vector <int> a; int n;

pair <int, int> dfs(int node, int parent)
{
    vector <pair<int, int>> s;
    pair <int, int> ans = { 0, 0 };

    for(auto& u : v[node]) if(u != parent) {
       s.push_back(dfs(u, node));
    }

    for(auto& u : s){
        if(a[node] == 0){
            ans.fs = min(u.fs, ans.fs);
            ans.sd = u.sd + ans.sd;
        }
        else{
            ans.fs = u.fs + ans.fs;
            ans.sd = min(u.sd, ans.sd);
        }
    }

    if(a[node] == 0) ans.sd ++;
    else ans.fs ++;

    //cerr << node << " " << a[node] << " " << parent << " " << ans.fs << " " << ans.sd << endl;

    return ans;
}

void solve()
{
    string s; cin >> s; 

    vector <int> p; int node = 0; n = 0;

    v.push_back(vector<int> ());
    p.push_back(-1);
    a.push_back(0);

    for(int i = 0; i < (int) s.size(); i++)
    {
        n += (s[i] == '?');

        if(s[i] == 'm'){
            if(node != 0) {
                v[node].push_back(v.size());
            }

            a.push_back((s[i+1] == 'a'));
            p.push_back(node); 
            node = v.size();
            v.push_back(vector<int> ());
        }

        if(s[i] == ')'){
            node = p[node];
        }
    }

   // cerr << n << endl;

    pair <int, int> ans = dfs(1, 0);

    cout << ((n - ans.sd) - ans.fs) << endl;
}

int32_t main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 171660 KB Output is correct
2 Correct 158 ms 178316 KB Output is correct
3 Correct 177 ms 178676 KB Output is correct
4 Correct 158 ms 178312 KB Output is correct
5 Correct 166 ms 178456 KB Output is correct
6 Correct 157 ms 178484 KB Output is correct
7 Correct 155 ms 178572 KB Output is correct
8 Correct 162 ms 178316 KB Output is correct
9 Correct 161 ms 178448 KB Output is correct
10 Correct 163 ms 178500 KB Output is correct
11 Correct 156 ms 178316 KB Output is correct
12 Correct 155 ms 178296 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -