oj.uz

Submission #165727

# Submission time Handle Problem Language Result Execution time Memory
165727 2019-11-28T11:56:21 Z Sensei Lozinke (COCI17_lozinke) C++17
10 / 100
 463 ms 65540 KB 
#include <bits/stdc++.h>

using namespace std;

const long long P = 53;
const long long MOD = 1e9 + 7;

const int MAXN = 2e4;

long long add (long long x, long long y) {
	return ((x % MOD) + (y % MOD)) % MOD;
}

long long mul (long long x, long long y) {
	return ((x % MOD) * (y % MOD)) % MOD;
}

unordered_map<long long, unordered_set<int> > m;
string st[MAXN + 7];
bool s[MAXN + 7][MAXN + 7];

int main () {
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> st[i];
	}

	for (int i = 1; i <= N; i++) {
		long long hash = 0;

		for (int j = 0; j < st[i].size(); j++) {
			hash = mul(hash, P);
			hash = add(hash, st[i][j] - 'a' + 1);
		}

		m[hash].insert(i);
	}

	long long ans = 0;

	for (int i = 1; i <= N; i++) {

		for (int ss = 0; ss < st[i].size(); ss++) {
			long long hash = 0;

			for (int j = ss; j < st[i].size(); j++) {
				if (ss == 0 && j + 1 == st[i].size()) {
					break;
				}

				hash = mul(hash, P);
				hash = add(hash, st[i][j] - 'a' + 1);

				if (m.find(hash) != m.end()) {
					for (int id : m[hash]) {
						if (id != i) {
							s[i][id] = s[id][i] = true;
						}
					}
				}
			}
		}

		for (int j = 1; j <= N; j++) {
			if (s[i][j]) {
				ans++;
			}
		}
	}

	long long ans2 = 0;

	for (int i = 1; i <= N; i++) {
		long long hash = 0;

		for (int j = 0; j < st[i].size(); j++) {
			hash = mul(hash, P);
			hash = add(hash, st[i][j] - 'a' + 1);
		}

		ans2 += m[hash].size() - 1;
	}

	ans += ans2;

	cout << ans << "\n";

	return 0;
}

Compilation message

lozinke.cpp: In function 'int main()':
lozinke.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < st[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~
lozinke.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int ss = 0; ss < st[i].size(); ss++) {
                    ~~~^~~~~~~~~~~~~~
lozinke.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = ss; j < st[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~
lozinke.cpp:49:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ss == 0 && j + 1 == st[i].size()) {
                    ~~~~~~^~~~~~~~~~~~~~~
lozinke.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < st[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1016 KB Output isn't correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Incorrect 3 ms 1400 KB Output isn't correct
4 Incorrect 6 ms 3320 KB Output isn't correct
5 Incorrect 11 ms 6108 KB Output isn't correct
6 Incorrect 17 ms 9336 KB Output isn't correct
7 Incorrect 24 ms 13148 KB Output isn't correct
8 Correct 14 ms 1272 KB Output is correct
9 Runtime error 203 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Incorrect 152 ms 3088 KB Output isn't correct
11 Runtime error 176 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Incorrect 299 ms 3216 KB Output isn't correct
13 Runtime error 119 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 137 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Incorrect 463 ms 4340 KB Output isn't correct
16 Runtime error 110 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 410 ms 2580 KB Output is correct
18 Runtime error 92 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 126 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 104 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)