Submission #990860

#	Time	Username	Problem	Language	Result	Execution time	Memory
990860		Savu_Stefan_Catalin	Homework (CEOI22_homework)	C++14	100 / 100	163 ms	236884 KiB

Main

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX=3e6+5;
int leaf[NMAX+5],sz[NMAX+5],st[NMAX+5],dr[NMAX+5],t[NMAX+5],vv[NMAX+5];
char s[3*NMAX+5];
vector <int> v[NMAX+5];
void dfs(int nod)
{
    if (leaf[nod]==1) {sz[nod]=1; st[nod]=1; dr[nod]=1; return ;}
    for (int i=0;i<2;++i)
    {
        dfs(v[nod][i]);
        sz[nod]+=sz[v[nod][i]];
    }
    int s=v[nod][0],d=v[nod][1];
    if (vv[nod]==0)
    {
        st[nod]=min(st[s],st[d]);
        dr[nod]=dr[s]+dr[d]-1;
    }
    else
    {
        st[nod]=st[s]+st[d];
        dr[nod]=max(dr[s]+sz[d],dr[d]+sz[s]);
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin.getline(s,8e6);
    int n=strlen(s);
    int p=0;
    int nod=0,cnt=0;
    while (true)
    {
        int val=0;
        if (s[p]=='m')
        {
            if (s[p+1]=='i') val=0;
            else val=1;
            cnt++;
            t[cnt]=nod;
            vv[cnt]=val;
            nod=cnt;
            p+=4;
        }
        else if (s[p]=='?')
        {
            cnt++;
            t[cnt]=nod;
            leaf[cnt]=1;
            p++;
        }
        else if (s[p]==')') {nod=t[nod]; p++;}
        else if (s[p]==',') p++;
        else break;
    }
    for (int i=1;i<=cnt;++i)
    {
        v[t[i]].push_back(i);
    }
    dfs(1);
    cout<<dr[1]-st[1]+1;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:9: warning: unused variable 'n' [-Wunused-variable]
   35 |     int n=strlen(s);
      |         ^

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