106222024-04-06 23:15:58111Forgó rulettkerékcpp17Hibás válasz 20/100379ms73400 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva3ms2052 KiB
subtask220/20
3Elfogadva3ms2244 KiB
4Elfogadva3ms2324 KiB
5Elfogadva3ms2712 KiB
6Elfogadva3ms2696 KiB
7Elfogadva4ms3288 KiB
8Elfogadva3ms2616 KiB
9Elfogadva4ms2936 KiB
subtask30/15
10Elfogadva23ms4232 KiB
11Elfogadva28ms5668 KiB
12Hibás válasz39ms8616 KiB
13Hibás válasz26ms5280 KiB
14Elfogadva26ms5852 KiB
15Hibás válasz90ms25672 KiB
16Hibás válasz137ms42180 KiB
17Hibás válasz93ms28852 KiB
subtask40/65
18Hibás válasz79ms13260 KiB
19Hibás válasz71ms8660 KiB
20Hibás válasz273ms43532 KiB
21Hibás válasz215ms42796 KiB
22Hibás válasz123ms23568 KiB
23Hibás válasz75ms9344 KiB
24Hibás válasz165ms31668 KiB
25Hibás válasz119ms18976 KiB
26Elfogadva92ms8636 KiB
27Hibás válasz133ms24392 KiB
28Elfogadva379ms73400 KiB
29Elfogadva96ms12672 KiB
30Elfogadva192ms34884 KiB