oj.uz

Submission #87173

# Submission time Handle Problem Language Result Execution time Memory
87173 2018-11-29T22:08:18 Z jasony123123 Lozinke (COCI17_lozinke) C++11
80 / 100
 818 ms 50608 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);
	}
	int 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 512 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 10 ms 1936 KB Output is correct
6 Correct 17 ms 2604 KB Output is correct
7 Correct 22 ms 3912 KB Output is correct
8 Correct 35 ms 6004 KB Output is correct
9 Correct 139 ms 11744 KB Output is correct
10 Incorrect 337 ms 24124 KB Output isn't correct
11 Correct 242 ms 24124 KB Output is correct
12 Correct 753 ms 48104 KB Output is correct
13 Correct 529 ms 48104 KB Output is correct
14 Incorrect 489 ms 48104 KB Output isn't correct
15 Incorrect 818 ms 50608 KB Output isn't correct
16 Correct 592 ms 50608 KB Output is correct
17 Correct 195 ms 50608 KB Output is correct
18 Correct 101 ms 50608 KB Output is correct
19 Incorrect 549 ms 50608 KB Output isn't correct
20 Correct 270 ms 50608 KB Output is correct