oj.uz

Submission #141438

# Submission time Handle Problem Language Result Execution time Memory
141438 2019-08-08T05:45:08 Z Vlatko Lozinke (COCI17_lozinke) C++14
0 / 100
 1000 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const ll mod = 1e9 + 7;
const ll prime = 31;
const int maxn = 20010;

int n;
string str[maxn];
ll prime_pow[maxn];
vector<ll> data[maxn];
unordered_map<ll, int> cnt;
ll ans;

void gen(int id, int pos, int len, ll hsh) {
    if (pos == str[id].length()) {
        if (len > 0) {
            data[id].push_back(hsh);
        }
    } else {
        gen(id, pos+1, len, hsh);
        gen(id, pos+1, len+1, (hsh + prime_pow[len]*(str[id][pos]-'a'+1)) % mod);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    prime_pow[0] = 1;
    for (int i = 1; i <= n; ++i) {
        prime_pow[i] = (prime_pow[i-1] * prime) % mod;
    }
    for (int id = 0; id < n; ++id) {
        cin >> str[id];
        gen(id, 0, 0, 0);
        sort(data[id].begin(), data[id].end());
        for (int i = 0; i < (int)data[id].size(); ++i) {
            if (i == 0 || data[id][i] != data[id][i-1]) {
                ++cnt[data[id][i]];
            }
        }
    }
    ans = 0;
    for (int id = 0; id < n; ++id) {
        ll hsh = 0;
        for (int pos = 0; pos < (int)str[id].length(); ++pos) {
            hsh = (hsh + prime_pow[pos]*(str[id][pos]-'a'+1)) % mod;
        }
        ans += cnt[hsh] - 1;
    }
    cout << ans << endl;
}

Compilation message

lozinke.cpp: In function 'void gen(int, int, int, ll)':
lozinke.cpp:46:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos == str[id].length()) {
         ~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1400 KB Output isn't correct
2 Incorrect 3 ms 1400 KB Output isn't correct
3 Incorrect 5 ms 1656 KB Output isn't correct
4 Incorrect 4 ms 1528 KB Output isn't correct
5 Incorrect 28 ms 4088 KB Output isn't correct
6 Incorrect 43 ms 5328 KB Output isn't correct
7 Incorrect 73 ms 8584 KB Output isn't correct
8 Incorrect 276 ms 18440 KB Output isn't correct
9 Incorrect 242 ms 20740 KB Output isn't correct
10 Execution timed out 1082 ms 62316 KB Time limit exceeded
11 Incorrect 420 ms 32312 KB Output isn't correct
12 Runtime error 861 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 723 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 818 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 854 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 548 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 280 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 314 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 1002 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Incorrect 364 ms 41584 KB Output isn't correct