106212024-04-06 23:13:54111Forgó rulettkerékcpp17Wrong answer 20/100377ms86056 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define MOD (int)1000000007
#define BASE (int)256

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[M+i]-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
1Accepted3ms1832 KiB
2Accepted3ms2028 KiB
subtask220/20
3Accepted3ms2252 KiB
4Accepted3ms2340 KiB
5Accepted3ms2372 KiB
6Accepted4ms2676 KiB
7Accepted4ms3448 KiB
8Accepted3ms3000 KiB
9Accepted4ms3332 KiB
subtask30/15
10Accepted20ms4872 KiB
11Accepted27ms6560 KiB
12Wrong answer37ms10280 KiB
13Wrong answer24ms7124 KiB
14Accepted24ms7888 KiB
15Wrong answer86ms27836 KiB
16Wrong answer134ms44604 KiB
17Wrong answer89ms31348 KiB
subtask40/65
18Wrong answer75ms16628 KiB
19Wrong answer64ms12996 KiB
20Wrong answer217ms48976 KiB
21Wrong answer244ms48960 KiB
22Wrong answer112ms30544 KiB
23Wrong answer71ms16972 KiB
24Wrong answer151ms40220 KiB
25Wrong answer108ms28792 KiB
26Accepted86ms19444 KiB
27Wrong answer123ms36068 KiB
28Accepted377ms86056 KiB
29Accepted93ms26504 KiB
30Accepted174ms49992 KiB