27592023-01-21 21:42:00CattForgó rulettkerékcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1968 KiB
2Elfogadva2ms2196 KiB
subtask220/20
3Elfogadva2ms2572 KiB
4Elfogadva2ms2592 KiB
5Elfogadva2ms3056 KiB
6Elfogadva3ms3468 KiB
7Elfogadva4ms5008 KiB
8Elfogadva3ms3896 KiB
9Elfogadva3ms4240 KiB
subtask315/15
10Elfogadva21ms7040 KiB
11Elfogadva27ms10592 KiB
12Elfogadva30ms17700 KiB
13Elfogadva23ms10556 KiB
14Elfogadva26ms10812 KiB
15Elfogadva57ms61080 KiB
16Elfogadva82ms118356 KiB
17Elfogadva57ms61156 KiB
subtask465/65
18Elfogadva68ms32308 KiB
19Elfogadva61ms18224 KiB
20Elfogadva123ms118420 KiB
21Elfogadva128ms118476 KiB
22Elfogadva89ms61300 KiB
23Elfogadva61ms18224 KiB
24Elfogadva116ms118492 KiB
25Elfogadva92ms61400 KiB
26Elfogadva92ms5564 KiB
27Elfogadva105ms61292 KiB
28Elfogadva179ms234440 KiB
29Elfogadva94ms10956 KiB
30Elfogadva118ms32360 KiB