Submission #735670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
735670	2023-05-04T12:47:43 Z	Nhoksocqt1	Rima (COCI17_rima)	C++17	140 / 140	294 ms	144352 KB

rima

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef long long ll;

struct TrieNode {
    int dp, cnt;
    TrieNode *next[27];

    TrieNode(int _f = 0, int _c = 0) {
        dp = _f, cnt = _c;
        for (int i = 0; i < 26; ++i) {
            next[i] = NULL;
        }
    }
} root;

string s;
int lcs[22][22], n, res;
bool f[(1 << 20) + 5][20];

void insert(TrieNode *cur, int h) {
    if(h < 0) {
        cur->cnt = 1;
        return;
    }

    if(!cur->next[s[h] - 'a']) {
        cur->next[s[h] - 'a'] = new TrieNode();
    }

    insert(cur->next[s[h] - 'a'], h - 1);
}

void dfs(TrieNode *cur) {
    int max1(0), max2(0), cnt(0);
    for (int i = 0; i < 26; ++i) {
        if(cur->next[i]) {
            dfs(cur->next[i]);
            cnt += cur->next[i]->cnt;
            if(max1 < cur->next[i]->dp) {
                max2 = max1;
                max1 = cur->next[i]->dp;
            } else
                if(max2 < cur->next[i]->dp) {
                    max2 = cur->next[i]->dp;
                }

            cur->dp = max(cur->dp, cur->next[i]->dp);
        }
    }

    if(cur->cnt) {
        cur->dp += 1 + max(0, cnt - 1);
    } else {
        cur->dp = 0;
    }

    res = max(res, max1 + max2 + cur->cnt + max(0, cnt - 2));
}

int sub1() {
    string s[n];
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int k(s[i].length() - 1), l(s[j].length() - 1);
            while(min(k, l) >= 0 && s[i][k] == s[j][l]) {
                ++lcs[i][j], ++lcs[j][i];
                --k, --l;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        f[(1 << i)][i] = 1;
    }

    int res(0);
    for (int mask = 1; mask < (1 << n); ++mask) {
        bool d(0);
        for (int i1 = mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1);
            if(!f[mask][i]) {
                continue;
            } else {
                d = 1;
            }

            for (int j1 = ((1 << n) - 1) ^ mask; j1 > 0; j1 ^= j1 & -j1) {
                int j = __builtin_ctz(j1 & -j1);
                if(lcs[i][j] >= int(max(s[i].length(), s[j].length())) - 1) {
                    f[mask | (1 << j)][j] = 1;
                }
            }
        }

        if(d) {
            res = max(res, __builtin_popcount(mask));
        }
    }

    return res;
}

void process() {
    cin >> n;
/*
    if(n <= 20) {
        cout << sub1();
        return;
    }*/

    res = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        insert(&root, s.length() - 1);
    }

    dfs(&root);
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

Compilation message

rima.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
rima.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	294 ms	144352 KB	Output is correct
5	Correct	10 ms	1108 KB	Output is correct
6	Correct	80 ms	99928 KB	Output is correct
7	Correct	65 ms	99748 KB	Output is correct
8	Correct	64 ms	99536 KB	Output is correct
9	Correct	80 ms	102880 KB	Output is correct
10	Correct	67 ms	99624 KB	Output is correct