Submission #141438

#TimeUsernameProblemLanguageResultExecution timeMemory
141438VlatkoLozinke (COCI17_lozinke)C++14
0 / 100
1082 ms65540 KiB
#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 (stderr)

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()) {
         ~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...