| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1084606 |
2024-09-06T13:37:36 Z |
lamlamlam |
Rima (COCI17_rima) |
C++17 |
|
1000 ms |
118716 KB |
#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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
33624 KB |
Output isn't correct |
| 2 |
Correct |
11 ms |
33372 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
33368 KB |
Output isn't correct |
| 4 |
Execution timed out |
1044 ms |
118716 KB |
Time limit exceeded |
| 5 |
Correct |
36 ms |
42320 KB |
Output is correct |
| 6 |
Incorrect |
16 ms |
35568 KB |
Output isn't correct |
| 7 |
Incorrect |
16 ms |
35200 KB |
Output isn't correct |
| 8 |
Incorrect |
16 ms |
34760 KB |
Output isn't correct |
| 9 |
Incorrect |
49 ms |
44892 KB |
Output isn't correct |
| 10 |
Incorrect |
16 ms |
34912 KB |
Output isn't correct |
