oj.uz

Submission #310456

# Submission time Handle Problem Language Result Execution time Memory
310456 2020-10-07T03:33:49 Z phathnv Parametriziran (COCI19_parametriziran) C++11
66 / 110
 169 ms 65540 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 640 KB Output is correct
2 Correct 12 ms 644 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 640 KB Output is correct
2 Correct 20 ms 760 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4096 KB Output is correct
2 Correct 17 ms 1920 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3320 KB Output is correct
2 Correct 29 ms 9088 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 30324 KB Output is correct
2 Correct 36 ms 4600 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -