oj.uz

Submission #96714

# Submission time Handle Problem Language Result Execution time Memory
96714 2019-02-11T11:20:11 Z polyfish Parametriziran (COCI19_parametriziran) C++14
110 / 110
 2328 ms 59408 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2040 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 2552 KB Output is correct
2 Correct 119 ms 2540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 2508 KB Output is correct
2 Correct 230 ms 2524 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 7368 KB Output is correct
2 Correct 171 ms 4088 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 6096 KB Output is correct
2 Correct 216 ms 7544 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 22324 KB Output is correct
2 Correct 228 ms 4280 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 26088 KB Output is correct
2 Correct 185 ms 4572 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1267 ms 39416 KB Output is correct
2 Correct 790 ms 22384 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1212 ms 36304 KB Output is correct
2 Correct 235 ms 4848 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2328 ms 59408 KB Output is correct
2 Correct 1314 ms 34936 KB Output is correct