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