oj.uz

Submission #87175

# Submission time Handle Problem Language Result Execution time Memory
87175 2018-11-29T22:13:05 Z jasony123123 Lozinke (COCI17_lozinke) C++11
80 / 100
 815 ms 49380 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define MOD 1000000009LL
#define PRIME 105943LL

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

map<ll, set<int>> substrKey;
int N;
ll hsh[20000];

ll calcHsh(string &str, int i, int j) {
	ll p = 1;
	ll ret = 0;
	FORE(x, i, j) {
		ret += (ll)(str[x])*p;
		ret %= MOD;
		p *= PRIME;
		p %= MOD;
	}
	return ret;
}

void setup(string &str, int idx) {
	FOR(i,0,str.size()) FOR(j, i, str.size()) {
		ll curhsh = calcHsh(str, i, j);
		substrKey[curhsh].insert(idx);
		if (i == 0 && j == str.size() - 1)
			hsh[idx] = curhsh;
	}
}

int main() {
	//io();
	cin >> N;
	FOR(i, 0, N) {
		string str;
		cin >> str;
		setup(str, i);
	}
	ll ans = 0;
	FOR(i, 0, N) {
		ans += substrKey[hsh[i]].size() - 1;
	}
	cout << ans << "\n";
	return 0;
}


void io() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// online submission
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Compilation message

lozinke.cpp: In function 'void setup(std::__cxx11::string&, int)':
lozinke.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == 0 && j == str.size() - 1)
                 ~~^~~~~~~~~~~~~~~~~
lozinke.cpp: In function 'void io()':
lozinke.cpp:70:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:71:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 672 KB Output is correct
5 Correct 13 ms 1744 KB Output is correct
6 Correct 17 ms 2528 KB Output is correct
7 Correct 22 ms 3668 KB Output is correct
8 Correct 35 ms 5752 KB Output is correct
9 Correct 135 ms 11528 KB Output is correct
10 Incorrect 291 ms 23656 KB Output isn't correct
11 Correct 234 ms 23656 KB Output is correct
12 Correct 736 ms 47592 KB Output is correct
13 Correct 523 ms 47592 KB Output is correct
14 Incorrect 496 ms 47592 KB Output isn't correct
15 Incorrect 815 ms 49380 KB Output isn't correct
16 Correct 577 ms 49380 KB Output is correct
17 Correct 189 ms 49380 KB Output is correct
18 Correct 90 ms 49380 KB Output is correct
19 Incorrect 524 ms 49380 KB Output isn't correct
20 Correct 246 ms 49380 KB Output is correct