Submission #81894

# Submission time Handle Problem Language Result Execution time Memory
81894 2018-10-27T15:30:50 Z ngot23 Rima (COCI17_rima) C++11
14 / 140
1000 ms 197444 KB
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=500005;
const int mod=1000000007;
const long long MM=1ll*mod*mod;
const int base=191;
long long h[3000001], Hash[3000001];
set <pair<int, int > > s[3000001];
string str[N];
int dp[N], n, mx, ans;

void setup() {
    cin >> n;
    rep(i, 1, n) {
        cin >> str[i];
        mx=max(mx, (int)str[i].size());
    }
}

long long get(int u, int v) {
    return (Hash[v]-Hash[u-1]*h[v-u+1]+MM)%mod;
}

void xuli(int id) {
    string ss=str[id];
    int leng=ss.size();
    ss=' '+ss;
    rep(i, 1, leng) {
        Hash[i]=(Hash[i-1]*base+ss[i])%mod;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    setup();
    h[0]=1;
    rep(i, 1, mx) h[i]=(h[i-1]*base)%mod;
    rep(i, 1, n) {
        dp[i]=1;
        xuli(i);
        int leng=str[i].size();
        long long hash2=get(2, leng);
        if(s[leng].size()) {
            auto it=s[leng].upper_bound(make_pair(Hash[leng], 1000000000));
            if(it!=s[leng].begin()) {
                --it;
                if(it->first==Hash[leng])
                    dp[i]=max(dp[i], dp[it->second]+1);
            }

            it=s[leng].upper_bound(make_pair(hash2, 1000000000));
            if(it!=s[leng].begin()) {
                --it;
                if(it->first==hash2) dp[i]=max(dp[i], dp[it->second]+1);
            }
        }

        if(s[leng+1].size()) {
            auto it=s[leng+1].upper_bound(make_pair(Hash[leng], 1000000000));
            if(it!=s[leng+1].begin()) {
                --it;
                if(it->first==Hash[leng]) dp[i]=max(dp[i], dp[it->second]+1);
            }
        }

        s[leng].insert(make_pair(Hash[n], i));
        s[leng].insert(make_pair(hash2, i));
    }
    rep(i, 1, n) ans=max(ans, dp[i]);
    cout << ans;
    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 157048 KB Output isn't correct
2 Correct 140 ms 157060 KB Output is correct
3 Incorrect 149 ms 157164 KB Output isn't correct
4 Execution timed out 1096 ms 197444 KB Time limit exceeded
5 Incorrect 175 ms 197444 KB Output isn't correct
6 Incorrect 160 ms 197444 KB Output isn't correct
7 Incorrect 169 ms 197444 KB Output isn't correct
8 Incorrect 159 ms 197444 KB Output isn't correct
9 Incorrect 204 ms 197444 KB Output isn't correct
10 Incorrect 153 ms 197444 KB Output isn't correct