Submission #1030405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030405		caterpillow	Savez (COCI15_savez)	C++17	108 / 120	91 ms	65536 KiB

savez

#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

/*

if a < b and b < c, then a < c
use string hashing

*/

const int m = 27;
const ll mod = 1e9 + 7;
const ll mx = 2e6 + 1;
ll powm[mx];

int n;
vt<vt<int>> adj;
vt<int> dp;
unordered_map<ll, int> seen;

void push_back(pl& hash, int c) {
    hash = {(hash.f * m + c + 1) % mod, hash.s + 1};
}

void push_front(pl& hash, int c) {
    hash = {(powm[hash.s] * (c + 1) + hash.f) % mod, hash.s + 1};
}

const pl hid = {0, 0};

int dfs(int u) {
    if (dp[u] != -1) return dp[u];
    int res = 0;
    for (int v : adj[u]) {
        res = max(res, dfs(v));
    }
    return dp[u] = res + 1;
}

main() {
    cin.tie(0)->sync_with_stdio(0);

    powm[0] = 1;
    FOR (i, 1, mx) powm[i] = (powm[i - 1] * m) % mod;

    cin >> n;
    adj.resize(n);
    dp.resize(n, -1);
    seen.reserve(n);
    F0R (i, n) {
        pl lhs = hid, rhs = hid;
        string st; cin >> st;
        vt<int> a(size(st)); F0R (i, size(st)) a[i] = st[i] - 'A';
        F0R (j, size(st)) {
            push_back(lhs, a[j]);
            push_front(rhs, a[size(st) - j - 1]);
            if (lhs.f == rhs.f) {
                auto it = seen.find(lhs.f);
                if (it != seen.end()) {
                    adj[it->s].pb(i);
                }
            }
        }
        seen[lhs.f] = i;
    }
    F0R (i, n) dfs(i);
    cout << *max_element(all(dp)) << endl;
}

Compilation message (stderr)

savez.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main() {
      | ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 0 / 12