Submission #600250

#	Time	Username	Problem	Language	Result	Execution time	Memory
600250		nguyen31hoang08minh2003	Rima (COCI17_rima)	C++14	14 / 140	329 ms	105076 KiB

rima

#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

class Trie {
private:
    int n;
    vi cnt, dp;
    vvi trie;
public:
    Trie(): n(0), cnt(1), trie(1, vi(26, -1)) {};

    void append(const string &s) {
        int x = 0, y;
        for (const char &c : s) {
            y = c - 'a';
            if (trie[x][y] < 0) {
                trie[x][y] = ++n;
                trie.pb(vi(26, -1));
                cnt.pb(0);
            }
            x = trie[x][y];
        }
        ++cnt[x];
    }

    int DP(int x) {
        if (dp[x] < 0) {
            dp[x] = 0;
            fore(y, 0, 26)
                if (trie[x][y] >= 0 && cnt[trie[x][y]] > 0)
                    maxi(dp[x], DP(trie[x][y]));
            fore(y, 0, 26)
                if (trie[x][y] >= 0)
                    dp[x] += cnt[trie[x][y]];
        }
        return dp[x];
    }

    int solve() {
        dp.resize(n + 1, -1);
        return DP(0);
    }

};

const int maxN = 5e5 + 5;

int n;
string word[maxN];
Trie trie;

void input() {
    cin >> n;
    fore(i, 0, n) {
        cin >> word[i];
        reverse(all(word[i]));
    }
}

void subtask1() {
    const int base = 2003, MOD = 1e9 + 9999, N = n + 5;
    int res = 0, length = 0, power[N];
    vvi lcp(N, vi(N)), dp(1 << n, vi(n));
    vector<vector<bool> > seen(1 << n, vector<bool>(n, false));
    vi h[N];
    const function<int(vi, int, int)> query = [&](const vi &h, const int l, const int r) -> int {
        return (h[r] - 1LL * h[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
    };
    const function<int(int, int)> findLCP = [&](int x, int y) -> int {
        const int a = word[x].size(), b = word[y].size();
        int lo = 0, hi = min(a, b) + 1, mid;
        while (lo + 1 < hi) {
            mid = lo + hi >> 1;
            if (query(h[x], 1, mid) == query(h[y], 1, mid))
                lo = mid;
            else
                hi = mid;
        }
        return lo;
    };
    const function<bool(int, int)> checkConnected = [&](const int a, const int b) -> bool {
        return lcp[a][b] >= max(sz(word[a]), sz(word[b])) - 1;
    };
    const function<int(int, int)> DP = [&](const int mask, const int x) -> int {
        if (!seen[mask][x]) {
            seen[mask][x] = true;
            dp[mask][x] = 1;
            fore(y, 0, n)
                if (!(mask & (1 << y)) && checkConnected(x, y))
                    maxi(dp[mask][x], 1 + DP(mask | (1 << y), y));
        }
        return dp[mask][x];
    };
    power[0] = 1;
    fore(i, 0, n) {
        maxi(length, word[i].size());
        h[i].pb(0);
        for (const char &c : word[i])
            h[i].pb((1LL * h[i].back() * base % MOD + c) % MOD);
    }
    fort(i, 1, length)
        power[i] = 1LL * power[i - 1] * base % MOD;
    fore(x, 0, n)
        fore(y, 0, n)
            lcp[x][y] = findLCP(x, y);
//    fore(x, 0, n)
//        fore(y, 0, n)
//            cerr << x << ' ' << y << ' ' << lcp[x][y] << '\n';
    fore(x, 0, n)
        maxi(res, DP(1 << x, x));
    cout << res << '\n';
}

void subtask2() {
    fore(i, 0, n)
        trie.append(word[i]);
    cout << trie.solve() << '\n';
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    input();
//    if (n <= 18)
//        subtask1();
//    else
        subtask2();
    return 0;
}

Compilation message (stderr)

rima.cpp: In lambda function:
rima.cpp:94:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             mid = lo + hi >> 1;
      |                   ~~~^~~~
rima.cpp: In instantiation of 'bool maxi(A&, const B&) [with A = int; B = long unsigned int]':
rima.cpp:117:36:   required from here
rima.cpp:15:67: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   15 | template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
      |                                                                ~~~^~~~

• Subtask 1: 14 / 140