10621 2024. 04. 06 23:13:54 111 Forgó rulettkerék cpp17 Hibás válasz 20/100 377ms 86056 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Elfogadva 3ms 2028 KiB
subtask2 20/20
3 Elfogadva 3ms 2252 KiB
4 Elfogadva 3ms 2340 KiB
5 Elfogadva 3ms 2372 KiB
6 Elfogadva 4ms 2676 KiB
7 Elfogadva 4ms 3448 KiB
8 Elfogadva 3ms 3000 KiB
9 Elfogadva 4ms 3332 KiB
subtask3 0/15
10 Elfogadva 20ms 4872 KiB
11 Elfogadva 27ms 6560 KiB
12 Hibás válasz 37ms 10280 KiB
13 Hibás válasz 24ms 7124 KiB
14 Elfogadva 24ms 7888 KiB
15 Hibás válasz 86ms 27836 KiB
16 Hibás válasz 134ms 44604 KiB
17 Hibás válasz 89ms 31348 KiB
subtask4 0/65
18 Hibás válasz 75ms 16628 KiB
19 Hibás válasz 64ms 12996 KiB
20 Hibás válasz 217ms 48976 KiB
21 Hibás válasz 244ms 48960 KiB
22 Hibás válasz 112ms 30544 KiB
23 Hibás válasz 71ms 16972 KiB
24 Hibás válasz 151ms 40220 KiB
25 Hibás válasz 108ms 28792 KiB
26 Elfogadva 86ms 19444 KiB
27 Hibás válasz 123ms 36068 KiB
28 Elfogadva 377ms 86056 KiB
29 Elfogadva 93ms 26504 KiB
30 Elfogadva 174ms 49992 KiB