Submission #1084606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084606		lamlamlam	Rima (COCI17_rima)	C++17	28 / 140	1044 ms	118716 KiB

rima

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MN = 5e5+5,mod0 = 1e9+7,mod1 = 1e9+9,base0 = 331,base1 = 293;
struct HASH
{
    int Hash[2] = {0,0};
    bool operator < (const HASH &o) const
    {
        if(Hash[0]!=o.Hash[0]) return Hash[0] < o.Hash[0];
        if(Hash[1]!=o.Hash[1]) return Hash[1] < o.Hash[1];
        return false;
    }
    HASH operator + (const char o) const
    {
        HASH res;
        res.Hash[0] = (Hash[0]*base0 + o)%mod0;
        res.Hash[1] = (Hash[1]*base1 + o)%mod1;
        return res;
    }
};
int n,dp[MN];
vector<int> v;
string s[MN],a[MN];
map<HASH,int> best,cnt;
bool cmp(int x,int y)
{
    return s[x].size() < s[y].size();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #define task "COCI17_rima"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n;
    for(int i=1; i<=n; i++) cin >> s[i],v.push_back(i);
    sort(v.begin(),v.end(),cmp);
    int ans = 1;
    for(int i=1; i<=n; i++) {
        dp[i] = 1;
        a[i] = s[v[i-1]];
        HASH hash_string[2];
        for(int j=a[i].size()-1; j>0; j--) hash_string[1] = hash_string[1] + a[i][j];
        hash_string[0] = hash_string[1] + a[i][0];
        //cout << hash_string[0].Hash[1] << ' ' << hash_string[1].Hash[1] << ' ' << a[i] << endl;
        if(cnt[hash_string[0]]) dp[i] = max(dp[i],1 + best[hash_string[0]]);
        if(cnt[hash_string[1]]) dp[i] = max(dp[i],1 + best[hash_string[1]]);
        //cout << endl;
        best[hash_string[0]] = max(best[hash_string[0]],dp[i]);
        best[hash_string[1]] = max(best[hash_string[1]],dp[i]);
        cnt[hash_string[0]]++;
        cnt[hash_string[1]]++;
        ans = max(ans,dp[i]);
    }
    //for(int i=1; i<=n; i++) cout << dp[i] << ' ';
    cout << ans;
    cerr << "\nTime: " << clock() << endl;
}

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
rima.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 140