oj.uz

Submission #991092

# Submission time Handle Problem Language Result Execution time Memory
991092 2024-06-01T09:17:41 Z andrei_iorgulescu Homework (CEOI22_homework) C++14
13 / 100
 91 ms 101996 KB 
#include <bits/stdc++.h>

using namespace std;

string a;
int poz;
int curnod = 1;
int l[4000005],r[4000005],s[4000005];
int fs[4000005],fd[4000005],tip[4000005];

void build_tree(int nod)
{
    if (a[poz] != '?')
    {
        if (a[poz + 1] == 'i')
            tip[nod] = 0;
        else
            tip[nod] = 1;
        poz += 4;
        curnod++;
        fs[nod] = curnod;
        build_tree(curnod);
        poz++;
        curnod++;
        fd[nod] = curnod;
        build_tree(curnod);
        poz++;
    }
    else
    {
        tip[nod] = -1;
        fs[nod] = fd[nod] = -1;
        poz++;
    }
}

void dfs(int nod)
{
    if (fs[nod] == -1)
        l[nod] = r[nod] = s[nod] = 1;
    else
    {
        dfs(fs[nod]);
        dfs(fd[nod]);
        s[nod] = s[fs[nod]] + s[fd[nod]];
        if (tip[nod] == 0)
        {
            l[nod] = min(l[fs[nod]],l[fd[nod]]);
            r[nod] = r[fs[nod]] + r[fd[nod]] - 1;
        }
        else
        {
            l[nod] = l[fs[nod]] + l[fd[nod]];
            r[nod] = max(l[fs[nod]] + s[fd[nod]],l[fd[nod]] + s[fs[nod]]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a;
    build_tree(1);
    dfs(1);
    cout << r[1] - l[1] + 1;
    return 0;
}

/**
Construiesc arborele ala
Fiecare nod poate avea un interval
Daca e frunza, e L = R = S = 1
Fie L1 R1 S1 si L2 R2 S2 L,R si size-ul pentru fii
S = S1 + S2 oricum
Daca e nod de min, L = min(L1,L2), R = R1 + R2 - 1
Daca e nod de max, L = L1 + L2 + 1, R = max(L1 + S2,L2 + S1)
**/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Incorrect 1 ms 10588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Incorrect 1 ms 10588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 101584 KB Output is correct
2 Correct 74 ms 101268 KB Output is correct
3 Correct 91 ms 101084 KB Output is correct
4 Correct 79 ms 101324 KB Output is correct
5 Correct 70 ms 101152 KB Output is correct
6 Correct 74 ms 101568 KB Output is correct
7 Correct 71 ms 100928 KB Output is correct
8 Correct 77 ms 101548 KB Output is correct
9 Correct 72 ms 101108 KB Output is correct
10 Correct 74 ms 101324 KB Output is correct
11 Correct 68 ms 101996 KB Output is correct
12 Correct 83 ms 101836 KB Output is correct
13 Correct 1 ms 10584 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Incorrect 1 ms 10588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Incorrect 1 ms 10588 KB Output isn't correct
6 Halted 0 ms 0 KB -