106232024-04-06 23:19:00111Forgó rulettkerékcpp17Elfogadva 100/100876ms112032 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define MOD 1000000007
#define BASE1 256
#define BASE2 468

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);
	map<pair<int,int>,int>m;
	for(int k=0;k<N;k++){
		string S;
		cin>>S;
		S+=S;
		vector<int>h1(M*2+1),h2(M*2+1),p1(M*2+1),p2(M*2+1);
		p1[0]=1;
		p2[0]=1;
		for(int i=0;i<M*2;i++){
			h1[i+1]=(h1[i]*BASE1+S[i])%MOD;
			h2[i+1]=(h2[i]*BASE2+S[i])%MOD;
			p1[i+1]=p1[i]*BASE1%MOD;
			p2[i+1]=p2[i]*BASE2%MOD;
		}
		for(int i=0;i<M;i++){
			int x1=(h1[i+M]-h1[i]*p1[M]%MOD+MOD)%MOD;
			int x2=(h2[i+M]-h2[i]*p2[M]%MOD+MOD)%MOD;
			auto t=m.find({x1,x2});
			if(t!=m.end()){
				dsu.unite(k,t->second);
			}
			else{
				m[{x1,x2}]=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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1836 KiB
2Elfogadva3ms2052 KiB
subtask220/20
3Elfogadva3ms2288 KiB
4Elfogadva3ms2488 KiB
5Elfogadva3ms2864 KiB
6Elfogadva4ms2996 KiB
7Elfogadva7ms4200 KiB
8Elfogadva4ms3320 KiB
9Elfogadva4ms3368 KiB
subtask315/15
10Elfogadva67ms5076 KiB
11Elfogadva78ms7068 KiB
12Elfogadva123ms12392 KiB
13Elfogadva75ms6964 KiB
14Elfogadva64ms7764 KiB
15Elfogadva244ms37784 KiB
16Elfogadva342ms49072 KiB
17Elfogadva298ms43216 KiB
subtask465/65
18Elfogadva273ms15996 KiB
19Elfogadva252ms10592 KiB
20Elfogadva680ms61052 KiB
21Elfogadva640ms54400 KiB
22Elfogadva398ms32148 KiB
23Elfogadva266ms11424 KiB
24Elfogadva578ms47816 KiB
25Elfogadva407ms27416 KiB
26Elfogadva209ms8692 KiB
27Elfogadva439ms32800 KiB
28Elfogadva876ms112032 KiB
29Elfogadva165ms14756 KiB
30Elfogadva524ms50856 KiB