10622 2024. 04. 06 23:15:58 111 Forgó rulettkerék cpp17 Hibás válasz 20/100 379ms 73400 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 3ms 2052 KiB
subtask2 20/20
3 Elfogadva 3ms 2244 KiB
4 Elfogadva 3ms 2324 KiB
5 Elfogadva 3ms 2712 KiB
6 Elfogadva 3ms 2696 KiB
7 Elfogadva 4ms 3288 KiB
8 Elfogadva 3ms 2616 KiB
9 Elfogadva 4ms 2936 KiB
subtask3 0/15
10 Elfogadva 23ms 4232 KiB
11 Elfogadva 28ms 5668 KiB
12 Hibás válasz 39ms 8616 KiB
13 Hibás válasz 26ms 5280 KiB
14 Elfogadva 26ms 5852 KiB
15 Hibás válasz 90ms 25672 KiB
16 Hibás válasz 137ms 42180 KiB
17 Hibás válasz 93ms 28852 KiB
subtask4 0/65
18 Hibás válasz 79ms 13260 KiB
19 Hibás válasz 71ms 8660 KiB
20 Hibás válasz 273ms 43532 KiB
21 Hibás válasz 215ms 42796 KiB
22 Hibás válasz 123ms 23568 KiB
23 Hibás válasz 75ms 9344 KiB
24 Hibás válasz 165ms 31668 KiB
25 Hibás válasz 119ms 18976 KiB
26 Elfogadva 92ms 8636 KiB
27 Hibás válasz 133ms 24392 KiB
28 Elfogadva 379ms 73400 KiB
29 Elfogadva 96ms 12672 KiB
30 Elfogadva 192ms 34884 KiB