10623 2024. 04. 06 23:19:00 111 Forgó rulettkerék cpp17 Elfogadva 100/100 876ms 112032 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1836 KiB
2 Elfogadva 3ms 2052 KiB
subtask2 20/20
3 Elfogadva 3ms 2288 KiB
4 Elfogadva 3ms 2488 KiB
5 Elfogadva 3ms 2864 KiB
6 Elfogadva 4ms 2996 KiB
7 Elfogadva 7ms 4200 KiB
8 Elfogadva 4ms 3320 KiB
9 Elfogadva 4ms 3368 KiB
subtask3 15/15
10 Elfogadva 67ms 5076 KiB
11 Elfogadva 78ms 7068 KiB
12 Elfogadva 123ms 12392 KiB
13 Elfogadva 75ms 6964 KiB
14 Elfogadva 64ms 7764 KiB
15 Elfogadva 244ms 37784 KiB
16 Elfogadva 342ms 49072 KiB
17 Elfogadva 298ms 43216 KiB
subtask4 65/65
18 Elfogadva 273ms 15996 KiB
19 Elfogadva 252ms 10592 KiB
20 Elfogadva 680ms 61052 KiB
21 Elfogadva 640ms 54400 KiB
22 Elfogadva 398ms 32148 KiB
23 Elfogadva 266ms 11424 KiB
24 Elfogadva 578ms 47816 KiB
25 Elfogadva 407ms 27416 KiB
26 Elfogadva 209ms 8692 KiB
27 Elfogadva 439ms 32800 KiB
28 Elfogadva 876ms 112032 KiB
29 Elfogadva 165ms 14756 KiB
30 Elfogadva 524ms 50856 KiB