2759 2023. 01. 21 21:42:00 Catt Forgó rulettkerék cpp17 Accepted 100/100 179ms 234440 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;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1968 KiB
2 Accepted 2ms 2196 KiB
subtask2 20/20
3 Accepted 2ms 2572 KiB
4 Accepted 2ms 2592 KiB
5 Accepted 2ms 3056 KiB
6 Accepted 3ms 3468 KiB
7 Accepted 4ms 5008 KiB
8 Accepted 3ms 3896 KiB
9 Accepted 3ms 4240 KiB
subtask3 15/15
10 Accepted 21ms 7040 KiB
11 Accepted 27ms 10592 KiB
12 Accepted 30ms 17700 KiB
13 Accepted 23ms 10556 KiB
14 Accepted 26ms 10812 KiB
15 Accepted 57ms 61080 KiB
16 Accepted 82ms 118356 KiB
17 Accepted 57ms 61156 KiB
subtask4 65/65
18 Accepted 68ms 32308 KiB
19 Accepted 61ms 18224 KiB
20 Accepted 123ms 118420 KiB
21 Accepted 128ms 118476 KiB
22 Accepted 89ms 61300 KiB
23 Accepted 61ms 18224 KiB
24 Accepted 116ms 118492 KiB
25 Accepted 92ms 61400 KiB
26 Accepted 92ms 5564 KiB
27 Accepted 105ms 61292 KiB
28 Accepted 179ms 234440 KiB
29 Accepted 94ms 10956 KiB
30 Accepted 118ms 32360 KiB