oj.uz

Submission #245167

# Submission time Handle Problem Language Result Execution time Memory
245167 2020-07-05T16:12:18 Z Vladikus004 Rima (COCI17_rima) C++14
14 / 140
 810 ms 128536 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 500000 + 3, LEN = 3000000 + 3, P = 31;
int n;
string s[N];
vector <ull> h[N];
ull deg[LEN];
unordered_map <ull, int> dp[2];

void init(){
    deg[0] = 1;
    for (int i = 1; i < LEN; i++)
        deg[i] = deg[i - 1] * P;
}

void make_hash(int ind){
    h[ind].resize(s[ind].size());
    h[ind][0] = s[ind][0] - 'a' + 1;
    for (int i = 1; i < s[ind].size(); i++)
        h[ind][i] = h[ind][i - 1] * P + (s[ind][i] - 'a' + 1);
}

ull get_hash(int ind, int l, int r){
    if (!l) return h[ind][r];
    return h[ind][r] - h[ind][l - 1] * deg[r - l + 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    init();
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        make_hash(i);
//        for (auto u: h[i]) cout << u << " ";
//        cout << "!\n";
    }
    int ans = 0;
    for (int i = n - 1; i >= 0; i--){
        ull hs1 = get_hash(i, 0, s[i].size() - 1);
        dp[1][hs1] = max(dp[1][hs1], dp[0][hs1]) + 1;
        ans = max(ans, dp[1][hs1]);
        if (s[i].size() != 1){
            ull hs = get_hash(i, 1, s[i].size() - 1);
            dp[0][hs] = max(dp[1][hs], dp[0][hs]) + 1;
            dp[0][hs] = max(dp[0][hs], dp[1][hs1]);
            dp[1][hs1] = max(dp[0][hs], dp[1][hs1]);
            ans = max(ans, dp[0][hs]);
        }
    }
    cout << ans;
}

Compilation message

rima.cpp: In function 'void make_hash(int)':
rima.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < s[ind].size(); i++)
                     ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 51200 KB Output isn't correct
2 Correct 34 ms 51200 KB Output is correct
3 Incorrect 31 ms 51192 KB Output isn't correct
4 Incorrect 810 ms 128536 KB Output isn't correct
5 Incorrect 71 ms 78328 KB Output isn't correct
6 Incorrect 45 ms 57616 KB Output isn't correct
7 Incorrect 43 ms 56480 KB Output isn't correct
8 Incorrect 37 ms 55640 KB Output isn't correct
9 Incorrect 86 ms 80980 KB Output isn't correct
10 Incorrect 37 ms 55816 KB Output isn't correct