10621 | 2024-04-06 23:13:54 | 111 | Forgó rulettkerék | cpp17 | Wrong answer 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1832 KiB | ||||
2 | Accepted | 3ms | 2028 KiB | ||||
subtask2 | 20/20 | ||||||
3 | Accepted | 3ms | 2252 KiB | ||||
4 | Accepted | 3ms | 2340 KiB | ||||
5 | Accepted | 3ms | 2372 KiB | ||||
6 | Accepted | 4ms | 2676 KiB | ||||
7 | Accepted | 4ms | 3448 KiB | ||||
8 | Accepted | 3ms | 3000 KiB | ||||
9 | Accepted | 4ms | 3332 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Accepted | 20ms | 4872 KiB | ||||
11 | Accepted | 27ms | 6560 KiB | ||||
12 | Wrong answer | 37ms | 10280 KiB | ||||
13 | Wrong answer | 24ms | 7124 KiB | ||||
14 | Accepted | 24ms | 7888 KiB | ||||
15 | Wrong answer | 86ms | 27836 KiB | ||||
16 | Wrong answer | 134ms | 44604 KiB | ||||
17 | Wrong answer | 89ms | 31348 KiB | ||||
subtask4 | 0/65 | ||||||
18 | Wrong answer | 75ms | 16628 KiB | ||||
19 | Wrong answer | 64ms | 12996 KiB | ||||
20 | Wrong answer | 217ms | 48976 KiB | ||||
21 | Wrong answer | 244ms | 48960 KiB | ||||
22 | Wrong answer | 112ms | 30544 KiB | ||||
23 | Wrong answer | 71ms | 16972 KiB | ||||
24 | Wrong answer | 151ms | 40220 KiB | ||||
25 | Wrong answer | 108ms | 28792 KiB | ||||
26 | Accepted | 86ms | 19444 KiB | ||||
27 | Wrong answer | 123ms | 36068 KiB | ||||
28 | Accepted | 377ms | 86056 KiB | ||||
29 | Accepted | 93ms | 26504 KiB | ||||
30 | Accepted | 174ms | 49992 KiB |