106222024-04-06 23:15:58111Forgó rulettkerékcpp17Wrong answer 20/100379ms73400 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define MOD 1000000007
#define BASE 61

struct DSU{
	vector<int>v;
	
	DSU(int n):v(n,-1){
	}
	
	int find(int i){
		return v[i]<0?i:v[i]=find(v[i]);
	}
	
	void unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b){
			return;
		}
		if(v[a]>v[b]){
			swap(a,b);
		}
		v[a]+=v[b];
		v[b]=a;
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	DSU dsu(N);
	unordered_map<int,int>m;
	for(int k=0;k<N;k++){
		string S;
		cin>>S;
		S+=S;
		vector<int>h(M*2+1),p(M*2+1);
		p[0]=1;
		for(int i=0;i<M*2;i++){
			h[i+1]=(h[i]*BASE+S[i])%MOD;
			p[i+1]=p[i]*BASE%MOD;
		}
		for(int i=0;i<M;i++){
			int x=(h[i+M]-h[i]*p[M]%MOD+MOD)%MOD;
			auto t=m.find(x);
			if(t!=m.end()){
				dsu.unite(k,t->second);
			}
			else{
				m[x]=k;
			}
		}
	}
	int ans=0;
	for(int i=0;i<N;i++){
		if(dsu.v[i]<0){
			int c=-dsu.v[i];
			ans+=c*(c-1)/2;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted3ms2052 KiB
subtask220/20
3Accepted3ms2244 KiB
4Accepted3ms2324 KiB
5Accepted3ms2712 KiB
6Accepted3ms2696 KiB
7Accepted4ms3288 KiB
8Accepted3ms2616 KiB
9Accepted4ms2936 KiB
subtask30/15
10Accepted23ms4232 KiB
11Accepted28ms5668 KiB
12Wrong answer39ms8616 KiB
13Wrong answer26ms5280 KiB
14Accepted26ms5852 KiB
15Wrong answer90ms25672 KiB
16Wrong answer137ms42180 KiB
17Wrong answer93ms28852 KiB
subtask40/65
18Wrong answer79ms13260 KiB
19Wrong answer71ms8660 KiB
20Wrong answer273ms43532 KiB
21Wrong answer215ms42796 KiB
22Wrong answer123ms23568 KiB
23Wrong answer75ms9344 KiB
24Wrong answer165ms31668 KiB
25Wrong answer119ms18976 KiB
26Accepted92ms8636 KiB
27Wrong answer133ms24392 KiB
28Accepted379ms73400 KiB
29Accepted96ms12672 KiB
30Accepted192ms34884 KiB