Submission #1138773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138773		bilgun	Homework (CEOI22_homework)	C++20	0 / 100	346 ms	589824 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<int> graph[2000001];
int par[2000001], n = 0, type[2000001], sz[2000001], mn[2000001], mx[2000001];

void dfs(int i) {
    if (graph[i].empty()) return;
    int u = graph[i][0], v = graph[i][1];
    
    dfs(u); 
    dfs(v); 
    
    sz[i] += sz[u] + sz[v];  
    
    if (type[i] == 1) { 
        mn[i] = min(mn[u], mn[v]);  
        mx[i] = mx[u] + mx[v] - 1; 
    } else if (type[i] == 2) {  
        mn[i] = mn[u] + mn[v];    
        mx[i] = max(sz[u] + mx[v], sz[v] + mx[u]);  
    }
}

int main() {
    string s;
    cin >> s;
    int curr = 0;
    
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'm') {  
            n++;
            par[n] = curr; 
            graph[curr].push_back(n); 
            curr = n;  
            if (i + 2 < s.size() && s[i + 2] == 'n') {
                type[curr] = 1; 
            } else {
                type[curr] = 2;  
            }
            i += 3;  
        } 
        else if (s[i] == '?') {  
            n++;
            graph[curr].push_back(n);  
            curr = n;  
            mn[curr] = mx[curr] = sz[curr] = 1; } 
        else { curr = par[curr];}
    }
    
    dfs(1);  
    cout << mx[1] - mn[1] + 1;
    
    return 0;
}

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