oj.uz

Submission #1030422

# Submission time Handle Problem Language Result Execution time Memory
1030422 2024-07-22T04:59:12 Z caterpillow Savez (COCI15_savez) C++17
84 / 120
 75 ms 65536 KB 
#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 = 2e6 + 7;

ll powm(ll y) {
    ll x = m;
    ll res = 1;
    while (y) {
        if (y & 1) res = (res * x) % mod;
        y >>= 1; 
        x = (x * x) % mod;
    }
    return res;
}

int n;
vt<int> adj[mod];
vt<int> dp;

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;
}

int arr[mod];

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

    memset(arr, -1, sizeof(arr));

    cin >> n;
    dp.resize(n, -1);
    F0R (i, n) {
        pl lhs = hid, rhs = hid;
        string st; cin >> st;
        F0R (j, size(st)) {
            push_back(lhs, st[j] - 'A');
            push_front(rhs, st[size(st) - j - 1] - 'A');
            if (lhs.f == rhs.f) {
                if (arr[lhs.f] != -1) {
                    adj[arr[lhs.f]].pb(i);
                }
            }
        }
        arr[lhs.f] = i;
    }
    F0R (i, n) dfs(i);
    cout << *max_element(all(dp)) << endl;
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 55120 KB Output is correct
2 Correct 27 ms 55132 KB Output is correct
3 Correct 26 ms 55132 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 55132 KB Output is correct
2 Correct 26 ms 55128 KB Output is correct
3 Correct 28 ms 55236 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 55128 KB Output is correct
2 Correct 63 ms 55128 KB Output is correct
3 Correct 75 ms 55628 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 55128 KB Output is correct
2 Correct 66 ms 55572 KB Output is correct
3 Incorrect 73 ms 55376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56664 KB Output is correct
2 Correct 51 ms 56920 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 58192 KB Output is correct
2 Correct 49 ms 58964 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 58704 KB Output is correct
2 Correct 48 ms 60228 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 59444 KB Output is correct
2 Correct 50 ms 62660 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -