Submission #116854

#	Time	Username	Problem	Language	Result	Execution time	Memory
116854		shuvi_dola	Lozinke (COCI17_lozinke)	C++14	100 / 100	927 ms	28416 KiB

lozinke

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;
const int N = 20003;
const long long A = 91382323;
const long long B = 1e9+7;

string s[N];
int h[N][13];
int pw[13];
set <pair<int,int> > tmp;
set <pair<int,int> > app;

map <int ,int> m[13];
map <int ,int> cnt[13];
map <int ,int> cnt1[13];
long long gethash(int l,int r,int pos)
{
	// cout<<h[pos][r]<<' '<<h[pos][l-1]<<'\n';
	return ( (h[pos][r] - h[pos][l-1]*pw[r-l+1]) % B + 10*B ) % B;
}


signed main()
{
	int n;
	cin>>n;
	pw[0] = 1;
	for(int i=1;i<13;i++)
	{
		pw[i] = (pw[i-1] * A) % B;
	}

	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		s[i] = "1" + s[i];
		int len = s[i].length();
		for(int j=1;j<len;j++)
		{
			h[i][j] = ( h[i][j-1]*A + (int)(s[i][j]) ) % B;
		}

		// cout<<h[i][len-1]<<'\n';
		app.insert({len-1, h[i][len-1]});
		cnt[len-1][h[i][len-1]]++;
	}

	for(int i=1;i<=n;i++)
	{
		tmp.clear();
		int len = s[i].length();

		for(int l=1;l<len;l++)
		{
			for(int r=l;r<len;r++)
			{
				if(l == 1 && r == len-1)
					continue;

				long long val = gethash(l,r,i);
				if(m[r-l+1][val] == false)
				{
					cnt1[r-l+1][val]++;
					m[r-l+1][val] = true;

					tmp.insert({r-l+1, val});
				}
				
			}
		}

		for(auto x:tmp)
		{
			m[x.fi][x.se] = false;
		}
	}

	long long ans = 0;
	for(auto x:app)
	{
		// cout<<x.fi<<' ';
		// cout<<cnt[x.fi][x.se]<<' '<<cnt1[x.fi][x.se]<<'\n';
		ans += cnt[x.fi][x.se] * (cnt[x.fi][x.se] - 1);
		ans += cnt[x.fi][x.se] * cnt1[x.fi][x.se];
	}
	cout<<ans;
}

• Subtask 1: 100 / 100