106212024-04-06 23:13:54111Forgó rulettkerékcpp17Hibás válasz 20/100377ms86056 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Elfogadva3ms2028 KiB
subtask220/20
3Elfogadva3ms2252 KiB
4Elfogadva3ms2340 KiB
5Elfogadva3ms2372 KiB
6Elfogadva4ms2676 KiB
7Elfogadva4ms3448 KiB
8Elfogadva3ms3000 KiB
9Elfogadva4ms3332 KiB
subtask30/15
10Elfogadva20ms4872 KiB
11Elfogadva27ms6560 KiB
12Hibás válasz37ms10280 KiB
13Hibás válasz24ms7124 KiB
14Elfogadva24ms7888 KiB
15Hibás válasz86ms27836 KiB
16Hibás válasz134ms44604 KiB
17Hibás válasz89ms31348 KiB
subtask40/65
18Hibás válasz75ms16628 KiB
19Hibás válasz64ms12996 KiB
20Hibás válasz217ms48976 KiB
21Hibás válasz244ms48960 KiB
22Hibás válasz112ms30544 KiB
23Hibás válasz71ms16972 KiB
24Hibás válasz151ms40220 KiB
25Hibás válasz108ms28792 KiB
26Elfogadva86ms19444 KiB
27Hibás válasz123ms36068 KiB
28Elfogadva377ms86056 KiB
29Elfogadva93ms26504 KiB
30Elfogadva174ms49992 KiB