Submission #96714

#	Time	Username	Problem	Language	Result	Execution time	Memory
96714		polyfish	Parametriziran (COCI19_parametriziran)	C++14	110 / 110	2328 ms	59408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cerr << #x << " = " << x << '\n';}
#define PR(a, n) {cerr << #a << " = "; for (int _=1; _<=n; ++_) cerr << a[_] << ' '; cerr << '\n';}
#define PR0(a, n) {cerr << #a << " = "; for (int _=0; _<n; ++_) cerr << a[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
 
const int M = 6;
const int MAX_N = 50002;
 
int n, H;
string s[MAX_N];
int64_t res;
map<int, int> mp;
 
void readInput() {
    int m;
 
    cin >> n >> m;
 
    for (int i=1; i<=n; ++i) {
        cin >> s[i];
        while (s[i].size()<M)
            s[i] += '?';
    }
}
 
void backtrack1(int idx, int pos) {
    if (s[idx][pos]=='?') {
        int tmp = H;
        H = H * 30 + 28;
        if (pos==M-1) {
            // PR0(p, p.size());
            if (mp.count(H))
                res += mp[H];
        }
        else {
            backtrack1(idx, pos+1);
        }
        H = tmp;
    }
    else {
        for (int i=0; i<2; ++i) {
            int tmp = H;
            H = H * 30 + (i==0 ? s[idx][pos]-'a'+1 : 27);
            if (pos==M-1) {
                // PR0(p, p.size());
                if (mp.count(H))
                    res += mp[H];
            }
            else {
                backtrack1(idx, pos+1);
            }
            H = tmp;
        }
    }
}
 
void backtrack2(int idx, int pos) {
    for (int i=0; i<2; ++i) {
        int tmp = H;
        if (i==0)
            H = H * 30 + 28;
        else
            H = H * 30 + (s[idx][pos]=='?' ? 27 : s[idx][pos]-'a'+1);
        if (pos==M-1) {
            // PR0(p, p.size());
            ++mp[H];
        }
        else {
            backtrack2(idx, pos+1);
        }
        H = tmp;
    }
}
 
void solve() {
    for (int i=1; i<=n; ++i) {
        backtrack1(i, 0);
        backtrack2(i, 0);
    }
 
    cout << res;
}
 
int main() {
    #ifdef GLASSES_GIRL
        freopen(FILE_NAME".inp", "r", stdin);
        freopen(FILE_NAME".out", "w", stdout);
    #endif
    readInput();
    solve();
}

• 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: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11