Submission #65270271

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    vector<array<int,26>> xt(1), yt(1);
    vector<bool> xterm(1,false), blocked;
    vector<vector<int>> yids(1);
    int Ycnt = 0, blocked_cnt = 0;
    while(Q--){
        int T;
        string s;
        cin >> T >> s;
        if(T == 1){
            int u = 0;
            for(char c : s){
                int d = c - 'a';
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    vector<array<int,26>> xt(1), yt(1);
    vector<bool> xterm(1,false), blocked;
    vector<vector<int>> yids(1);
    int Ycnt = 0, blocked_cnt = 0;

    while(Q--){
        int T;
        string s;
        cin >> T >> s;
        if(T == 1){
            int u = 0;
            for(char c : s){
                int d = c - 'a';
                if(!xt[u][d]){
                    xt[u][d] = xt.size();
                    xt.emplace_back();
                    xterm.push_back(false);
                }
                u = xt[u][d];
            }
            xterm[u] = true;
            int v = 0;
            bool ok = true;
            for(char c : s){
                int d = c - 'a';
                if(!yt[v][d]){ ok = false; break; }
                v = yt[v][d];
            }
            if(ok){
                for(int id : yids[v])
                    if(!blocked[id]){
                        blocked[id] = true;
                        blocked_cnt++;
                    }
                yids[v].clear();
            }
        } else {
            int yid = Ycnt++;
            blocked.push_back(false);
            int u = 0;
            bool is_block = false;
            for(char c : s){
                if(xterm[u]){ is_block = true; break; }
                int d = c - 'a';
                if(!xt[u][d]){ u = -1; break; }
                u = xt[u][d];
            }
            if(u >= 0 && xterm[u]) is_block = true;
            if(is_block){
                blocked[yid] = true;
                blocked_cnt++;
            } else {
                int v = 0;
                for(char c : s){
                    int d = c - 'a';
                    if(!yt[v][d]){
                        yt[v][d] = yt.size();
                        yt.emplace_back();
                        yids.emplace_back();
                    }
                    v = yt[v][d];
                    yids[v].push_back(yid);
                }
            }
        }
        cout << (Ycnt - blocked_cnt) << "\n";
    }
    return 0;
}

Submission Info

Judge Result