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