Submission #310456

#	Time	Username	Problem	Language	Result	Execution time	Memory
310456		phathnv	Parametriziran (COCI19_parametriziran)	C++11	66 / 110	169 ms	65540 KiB

Main

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Parametriziran"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

struct trieNode{
    int cnt;
    trieNode *child[28];
    trieNode(){
        cnt = 0;
        for(int i = 0; i < 28; i++)
            child[i] = NULL;
    }
    int getInd(char ch){
        return (ch == '?'? 26 : ch - 'a');
    }
    void add(string &s){
        if (s.empty()){
            cnt++;
            return;
        }
        char ch = s.back();
        int ind = getInd(ch);
        s.pop_back();

        if (child[ind] == NULL)
            child[ind] = new trieNode;
        child[ind] -> add(s);
        if (child[27] == NULL)
            child[27] = new trieNode;
        child[27] -> add(s);

        s.push_back(ch);
    }
    int get(string &s){
        if (s.empty())
            return cnt;
        char ch = s.back();
        int ind = getInd(ch) + (ch == '?');
        s.pop_back();

        int res = 0;

        if (child[ind] != NULL)
            res += child[ind] -> get(s);
        if (child[26] != NULL && ind != 27)
            res += child[26] -> get(s);

        s.push_back(ch);
        return res;
    }
};

trieNode *trie = new trieNode;

int n, m;

void readInput(){
    cin >> n >> m;
}

void solve(){
    ll res = 0;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        res += trie -> get(s);
        trie -> add(s);
    }
    cout << res;
}

int main(){
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    readInput();
    solve();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11