oj.uz

Submission #96712

# Submission time Handle Problem Language Result Execution time Memory
96712 2019-02-11T11:10:59 Z polyfish Parametriziran (COCI19_parametriziran) C++14
66 / 110
 1374 ms 66560 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;        ///notice
const int MAX_N = 50002;

int n;
string s[MAX_N];
vector<int> p(M);
int64_t res;
map<vector<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]=='?') {
        p[pos] = -1;
        if (pos==M-1) {
            // PR0(p, p.size());
            res += mp[p];
        }
        else {
            backtrack1(idx, pos+1);
        }
    }
    else {
        for (int i=0; i<2; ++i) {
            p[pos] = (i==0 ? s[idx][pos]-'a' : 26);
            if (pos==M-1) {
                // PR0(p, p.size());
                res += mp[p];
            }
            else {
                backtrack1(idx, pos+1);
            }
        }
    }
}

void backtrack2(int idx, int pos) {
    for (int i=0; i<2; ++i) {
        if (i==0)
            p[pos] = -1;
        else
            p[pos] = (s[idx][pos]=='?' ? 26 : s[idx][pos]-'a');
        if (pos==M-1) {
            // PR0(p, p.size());
            ++mp[p];
        }
        else {
            backtrack2(idx, pos+1);
        }
    }
}

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 258 ms 2040 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 3192 KB Output is correct
2 Correct 245 ms 3292 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 3288 KB Output is correct
2 Correct 469 ms 3492 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 14664 KB Output is correct
2 Correct 363 ms 6852 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 11624 KB Output is correct
2 Correct 411 ms 15452 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 53704 KB Output is correct
2 Correct 490 ms 7544 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1244 ms 66560 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 815 ms 66560 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 784 ms 66560 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 740 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -