oj.uz

Submission #956795

# Submission time Handle Problem Language Result Execution time Memory
956795 2024-04-02T13:18:42 Z Lukap Homework (CEOI22_homework) C++14
13 / 100
 181 ms 205228 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6;

string s;
int n, uk;
int l[MAXN], r[MAXN], tip[MAXN], lo[MAXN], hi[MAXN], vel[MAXN];
vector<int> v;
vector<int> zarez[MAXN];
int koji[MAXN];

void unos (int l_g, int r_g, int xi) {
    int x = uk;
    uk++;
    if (r_g == l_g) {
        n++;
        return;
    }

    char a = s[l_g + 1];

    int zag = zarez[xi][koji[xi]];
    koji[xi]++;

    if (a == 'i') tip[x] = 0;
    else tip[x] = 1;

    l[x] = uk;
    unos (l_g + 4, zag - 1, xi + 1);

    r[x] = uk;
    unos (zag + 1, r_g - 1, xi + 1);

}

void dfs (int x, int glavn) {
    if (l[x] == -1) {
        vel[glavn]++;
        lo[glavn] = 1;
        hi[glavn] = n;
        return;
    }

    if (tip[x] != tip[0]) {
        vel[glavn]++;
        dfs (l[x], x);
        dfs (r[x], x);
        if (!tip[x]) hi[x] -= vel[x] - 1;
        else lo[x] += vel[x] - 1;

        lo[glavn] = min (lo[glavn], lo[x]);
        hi[glavn] = max (hi[glavn], hi[x]);
    }

    else {
        dfs (l[x], glavn);
        dfs (r[x], glavn);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie (0);
    cout.tie (0);
    memset (l , -1, sizeof (l));
    memset (r, -1, sizeof (r));

    cin >> s;
    int brojem = 0;
    for (int i = 0; i < (int) s.size (); i++) {
        if (s[i] == '(') brojem++;
        if (s[i] == ')') brojem--;
        if (s[i] == ',') zarez[brojem - 1].push_back (i);
    }
    unos (0, s.size () - 1, 0);

    for (int i = 0; i < uk; i++) {
        lo[i] = n;
        hi[i] = 0;
    }

    dfs (0, 0);
    if (!tip[0]) hi[0] -= vel[0] - 1;
    else lo[0] += vel[0] - 1;

    cout << hi[0] - lo[0] + 1;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73044 KB Output is correct
2 Correct 16 ms 73308 KB Output is correct
3 Correct 15 ms 73308 KB Output is correct
4 Incorrect 17 ms 73308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73044 KB Output is correct
2 Correct 16 ms 73308 KB Output is correct
3 Correct 15 ms 73308 KB Output is correct
4 Incorrect 17 ms 73308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 171468 KB Output is correct
2 Correct 140 ms 177612 KB Output is correct
3 Correct 163 ms 192120 KB Output is correct
4 Correct 157 ms 191932 KB Output is correct
5 Correct 163 ms 205228 KB Output is correct
6 Correct 145 ms 184200 KB Output is correct
7 Correct 144 ms 184388 KB Output is correct
8 Correct 156 ms 184784 KB Output is correct
9 Correct 153 ms 191608 KB Output is correct
10 Correct 165 ms 191696 KB Output is correct
11 Correct 155 ms 192172 KB Output is correct
12 Correct 181 ms 192452 KB Output is correct
13 Correct 15 ms 73308 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73044 KB Output is correct
2 Correct 16 ms 73308 KB Output is correct
3 Correct 15 ms 73308 KB Output is correct
4 Incorrect 17 ms 73308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73044 KB Output is correct
2 Correct 16 ms 73308 KB Output is correct
3 Correct 15 ms 73308 KB Output is correct
4 Incorrect 17 ms 73308 KB Output isn't correct
5 Halted 0 ms 0 KB -