Submission #96616

#TimeUsernameProblemLanguageResultExecution timeMemory
96616FutymyCloneParametriziran (COCI19_parametriziran)C++14
77 / 110
3063 ms35884 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 5; int n, m; long long ans = 0; struct Trie { Trie *child[27]; int last; Trie(){ last = 0; for (int i = 0; i < 27; i++) child[i] = NULL; } } *root = new Trie(); void dfs (string s, int pos, Trie *cur) { if (pos == m) { cur -> last++; return; } if (s[pos] == '?') { if (cur -> child[26] == NULL) cur -> child[26] = new Trie(); dfs(s, pos + 1, cur -> child[26]); } else { if (cur -> child[s[pos] - 'a'] == NULL) cur -> child[s[pos] - 'a'] = new Trie(); dfs(s, pos + 1, cur -> child[s[pos] - 'a']); } } void solve (string s, int pos, Trie *cur) { if (pos == m) { ans += cur -> last; return; } if (s[pos] == '?') { for (int i = 0; i < 27; i++) { if (cur -> child[i] != NULL) solve(s, pos + 1, cur -> child[i]); } } else { if (cur -> child[s[pos] - 'a'] != NULL) solve(s, pos + 1, cur -> child[s[pos] - 'a']); if (cur -> child[26] != NULL) solve(s, pos + 1, cur -> child[26]); } } int main(){ //freopen("testgen.inp", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { string s; cin >> s; solve(s, 0, root); dfs(s, 0, root); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...