oj.uz

답안 #87178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
87178 2018-11-29T22:18:11 Z jasony123123 Lozinke (COCI17_lozinke) C++11
80 / 100
 873 ms 49404 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;
//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 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;
}

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:56: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:80: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:81: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 3 ms 664 KB Output is correct
5 Correct 12 ms 1748 KB Output is correct
6 Correct 19 ms 2644 KB Output is correct
7 Correct 26 ms 3872 KB Output is correct
8 Correct 41 ms 5920 KB Output is correct
9 Correct 141 ms 11612 KB Output is correct
10 Correct 312 ms 23776 KB Output is correct
11 Correct 251 ms 23776 KB Output is correct
12 Incorrect 752 ms 47624 KB Output isn't correct
13 Correct 531 ms 47624 KB Output is correct
14 Incorrect 470 ms 47624 KB Output isn't correct
15 Incorrect 873 ms 49404 KB Output isn't correct
16 Correct 604 ms 49404 KB Output is correct
17 Correct 193 ms 49404 KB Output is correct
18 Correct 91 ms 49404 KB Output is correct
19 Incorrect 512 ms 49404 KB Output isn't correct
20 Correct 273 ms 49404 KB Output is correct