Submission #144956

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
144956	2019-08-18T09:24:47 Z	darkkcyan	Rima (COCI17_rima)	C++14	70 / 140	927 ms	50404 KB

rima

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

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

#define rem ((llong) 1000027241)
#define base 29
#define maxn 501010

int dsu[maxn];
int set_cnt[maxn];
int find_set(int u) { return u == dsu[u] ? u : dsu[u] = find_set(dsu[u]); }
void join(int u, int v) {
    if (rand() & 1) swap(u, v);
    u = find_set(u); v = find_set(v);
    if (u == v) return ;
    set_cnt[u] += set_cnt[v];
    dsu[v] = u;
}

struct word {
    llong hash_code;
    int length;
    word(llong hc = 0, int l = 0): hash_code(hc), length(l) {}
    word(const string& s): hash_code(0), length(len(s)) {
        for (auto ch: s) 
            ((hash_code *= base) += ch - 'a' + 1) %= rem;
    }

    word add(char ch) {
        return word((hash_code * base + ch - 'a' + 1) % rem, length + 1);
    }
};

bool operator< (const word& u, const word& v) {
    if (u.length == v.length) return u.hash_code < v.hash_code;
    return u.length < v.length;
}

int n;
word words[maxn], pref_words[maxn];
vector<int> gr[maxn];

bool vis[maxn];
pair<int, int> dfs(int u) {
    pair<int, int> ans(set_cnt[u], set_cnt[u]);
    vis[u] = 1;
    for (auto v: gr[u]) {
        if (vis[v]) continue;
        auto temp = dfs(v);
        ans.xx = max(ans.xx, temp.xx);
        ans.xx = max(ans.xx, temp.yy + ans.yy);
        ans.yy = max(ans.yy, set_cnt[u] + temp.yy);
    }
    return ans;
}

int main(void) {
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, n) {
        string s; cin >> s;
        reverse(s.begin(), s.end());
        pref_words[i] = word(s.substr(0, len(s) - 1));
        words[i] = pref_words[i].add(s.back());
    }

    rep(i, n) {
        dsu[i] = i;
        set_cnt[i] = 1;
    }

    map<word, int> pref_pos;
    rep(i, n) {
        if (!pref_pos.count(pref_words[i])) 
            pref_pos[pref_words[i]] = i;
        else 
            join(i, pref_pos[pref_words[i]]);
    }

    rep(i, n) {
        if (!pref_pos.count(words[i])) continue;
        int u = find_set(i);
        int v = find_set(pref_pos[words[i]]);
        gr[u].emplace_back(v);
        gr[v].emplace_back(u);
    }

    int ans = 0;
    memset(vis, 0, sizeof vis);
    rep(i, n) {
        if (i != find_set(i) or vis[i]) continue;
        ans = max(ans, dfs(i).xx);
    }

    cout << ans;

    return 0;
}

Subtask #1

70.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	28280 KB	Output is correct
2	Correct	30 ms	28280 KB	Output is correct
3	Correct	26 ms	28280 KB	Output is correct
4	Correct	927 ms	50404 KB	Output is correct
5	Correct	51 ms	28536 KB	Output is correct
6	Incorrect	33 ms	28552 KB	Output isn't correct
7	Incorrect	32 ms	28572 KB	Output isn't correct
8	Incorrect	31 ms	28500 KB	Output isn't correct
9	Incorrect	74 ms	28948 KB	Output isn't correct
10	Incorrect	36 ms	28544 KB	Output isn't correct