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

rima

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

Subtask #1

14.0 / 140.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