27592023-01-21 21:42:00CattForgó rulettkerékcpp17Accepted 100/100179ms234440 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;


struct Node {
    int to[27];
    int cnt;

    Node() {
        for(int i = 0; i < 27; i++) {
            to[i] = -1;
        }
        cnt = 0;
    }
};

vector<Node> trie(1, Node());


string minimalRotation(const string &s) {
    int N = (int)s.size();
    int minPos = 0, l = 0, p = 1;
    while (p < N && minPos + l + 1 < N) {
        if (s[minPos + l] == s[(p + l) % N]) {
            l++;
        } else if (s[minPos + l] < s[(p + l) % N]) {
            p = p + l + 1;
            l = 0;
        } else {
            minPos = max(minPos + l + 1, p);
            p = minPos + 1;
            l = 0;
        }
    }
    
    string ans;
    for (int i = minPos; (int)ans.size() != N; i = (i + 1) % N) {
        ans.push_back(s[i]);
    }
    return ans;
}

void add(string s)
{
    int curr = 0;
    for(char c : s) {
        if(trie[curr].to[c - 'a'] == -1 ) {
            trie[curr].to[c - 'a'] = trie.size();
            trie.push_back(Node());
        }
        curr = trie[curr].to[c - 'a'];
        trie[curr].cnt++;
    }
}

int query(string s) {
    int curr = 0;
    for(char c : s) {
        if(trie[curr].to[c - 'a'] == -1) return 0;

        curr = trie[curr].to[c - 'a'];
    }

    return trie[curr].cnt;
} 


int main() {
    int n,m;
    cin >> n >> m;
    ll mo = 0;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;

        s = minimalRotation(s);
        mo += query(s);
        add(s);
    }
    cout << mo;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1968 KiB
2Accepted2ms2196 KiB
subtask220/20
3Accepted2ms2572 KiB
4Accepted2ms2592 KiB
5Accepted2ms3056 KiB
6Accepted3ms3468 KiB
7Accepted4ms5008 KiB
8Accepted3ms3896 KiB
9Accepted3ms4240 KiB
subtask315/15
10Accepted21ms7040 KiB
11Accepted27ms10592 KiB
12Accepted30ms17700 KiB
13Accepted23ms10556 KiB
14Accepted26ms10812 KiB
15Accepted57ms61080 KiB
16Accepted82ms118356 KiB
17Accepted57ms61156 KiB
subtask465/65
18Accepted68ms32308 KiB
19Accepted61ms18224 KiB
20Accepted123ms118420 KiB
21Accepted128ms118476 KiB
22Accepted89ms61300 KiB
23Accepted61ms18224 KiB
24Accepted116ms118492 KiB
25Accepted92ms61400 KiB
26Accepted92ms5564 KiB
27Accepted105ms61292 KiB
28Accepted179ms234440 KiB
29Accepted94ms10956 KiB
30Accepted118ms32360 KiB