oj.uz

Submission #237726

# Submission time Handle Problem Language Result Execution time Memory
237726 2020-06-08T12:52:41 Z akat Trener (COCI20_trener) C++14
22 / 110
 10 ms 3584 KB 
#include<bits/stdc++.h>
using namespace std;
const long long st[3]={127,131,137};
const long long mod[3]={123457,(long long)(1e7+7),(long long)(1e7+9)};
vector<long long>de[3];
void init(int n)
{
	int i,j;
	for(i=0;i<3;i++)
	{
		de[i].resize(n+1);
		de[i][0]=1;
		for(j=1;j<n+1;j++)
			de[i][j]=(de[i][j-1]*st[i])%mod[i];
	}
}
struct hash3
{
	long long h[3];
	int sz;
	hash3()
	{
		h[0]=h[1]=h[2]=0;
		sz=0;
	}
	hash3(string s)
	{
		h[0]=h[1]=h[2]=0;
		sz=0;
		for(int i=0;i<sz;i++)
			(*this)+=hash3(s[i]);
	}
	hash3(char c)
	{
		h[0]=h[1]=h[2]=c;
		sz=1;
	}
	hash3 operator=(hash3 const &x)
	{
		for(int i=0;i<3;i++)
			h[i]=x.h[i];
		sz=x.sz;
		return *this;
	}
	hash3 operator+(hash3 x)
	{
		hash3 ans;
		for(int i=0;i<3;i++)
			ans.h[i]=(h[i]*de[i][x.sz]+x.h[i])%mod[i];
		ans.sz=sz+x.sz;
		return ans;
	}
	hash3 operator+=(hash3 x)
	{
		(*this)=(*this)+x;
		return *this;
	}
	hash3 operator-(const hash3 &x)
	{
		hash3 ans;
		for(int i=0;i<3;i++)
		{
			ans.h[i]=h[i]-(de[i][sz-x.sz]*x.h[i])%mod[i];
			if(ans.h[i]<0)ans.h[i]+=mod[i];
		}
		ans.sz=sz-x.sz;
		return ans;
	}
	hash3 operator-=(hash3 x)
	{
		(*this)=(*this)-x;
		return *this;
	}
	bool operator==(hash3 const &a)
	{
		int i;
		for(i=0;i<3;i++)
			if(this->h[i]!=a.h[i])return 0;
		return 1;
	}
	bool operator!=(hash3 const &a)
	{
		return !(*this == a);
	}
};
struct HashTable
{
	vector<pair<hash3,long long>>ht[123457];
	void add(hash3 x,long long z)
	{
		for(auto &y:ht[x.h[0]])
			if(y.first == x)
			{
				y.second += z;
				return;
			}
		ht[x.h[0]].push_back({x,z});
	}
	long long query(hash3 x)
	{
		for(auto y:ht[x.h[0]])
			if(y.first == x)return y.second;
		return 0;
	}
}HT;
const int MOD = 1e9 + 7;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n,k,i,j,l,curr,ans = 0;
	string s;
	cin>>n>>k;
	init(n);
	for(i = 0; i < n; i++)
		for(j = 0; j < k; j++)
		{
			cin>>s;
			hash3 h;
			for(l = 0; l < (int)s.size() - 1; l++)
				h += hash3(s[l]);
			curr = HT.query(h);
			hash3 oldh = h;
			h += hash3(s[l]);
			hash3 p = h;
			p -= hash3(s[0]);
			if(p != oldh) curr += HT.query(p);
			if(curr >= MOD) curr -= MOD;
			if(i==0) curr++;
			HT.add(h, curr);
			if(i == n-1) ans += curr;
		}
	cout<<ans<<'\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 6 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3456 KB Output is correct
2 Correct 9 ms 3584 KB Output is correct
3 Correct 10 ms 3584 KB Output is correct
4 Incorrect 8 ms 3328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 6 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 9 ms 3584 KB Output is correct
7 Correct 10 ms 3584 KB Output is correct
8 Incorrect 8 ms 3328 KB Output isn't correct
9 Halted 0 ms 0 KB -