oj.uz

Submission #87179

# Submission time Handle Problem Language Result Execution time Memory
87179 2018-11-29T22:19:34 Z jasony123123 Lozinke (COCI17_lozinke) C++11
100 / 100
 824 ms 52696 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 MOD1 1000000009LL
#define MOD2 2038072819LL
#define PRI1 610639LL
#define PRI2 949957LL

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

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

pll calcHsh(string &str, int i, int j) {
	ll p1 = 1;
	ll ret1 = 0;
	FORE(x, i, j) {
		ret1 += (ll)(str[x])*p1;
		ret1 %= MOD1;
		p1 *= PRI1;
		p1 %= MOD1;
	}
	ll p2 = 1;
	ll ret2 = 0;
	FORE(x, i, j) {
		ret2 += (ll)(str[x])*p2;
		ret2 %= MOD2;
		p2 *= PRI2;
		p2 %= MOD2;
	}
	return{ ret1, ret2 };
}

void setup(string &str, int idx) {
	FOR(i,0,str.size()) FOR(j, i, str.size()) {
		pll 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:57: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:81: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:82: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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 648 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 12 ms 1916 KB Output is correct
6 Correct 19 ms 2620 KB Output is correct
7 Correct 40 ms 3892 KB Output is correct
8 Correct 54 ms 6136 KB Output is correct
9 Correct 139 ms 12016 KB Output is correct
10 Correct 312 ms 25256 KB Output is correct
11 Correct 247 ms 25256 KB Output is correct
12 Correct 736 ms 50704 KB Output is correct
13 Correct 564 ms 50704 KB Output is correct
14 Correct 497 ms 50704 KB Output is correct
15 Correct 824 ms 52696 KB Output is correct
16 Correct 588 ms 52696 KB Output is correct
17 Correct 228 ms 52696 KB Output is correct
18 Correct 103 ms 52696 KB Output is correct
19 Correct 556 ms 52696 KB Output is correct
20 Correct 294 ms 52696 KB Output is correct