| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167794 |
2019-12-10T07:14:58 Z |
egekabas |
Rima (COCI17_rima) |
C++14 |
|
386 ms |
98044 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n;
string s[500009];
int edge[3000000][30];
int part[3000000];
int full[3000000];
int dp[3000000];
int cur = 2;
int ans;
int go(int root, char c){
int tmp = (int)(c - 'a');
if(edge[root][tmp] != 0)
return edge[root][tmp];
return edge[root][tmp] = cur++;
}
void add(string s){
int root = 1;
for(int i = 0; i < s.size(); ++i){
root = go(root, s[i]);
if(i == s.size()-2 || (i == 0 && s.size() == 1))
part[root]++;
if(i == s.size()-1)
full[root]++;
}
}
int f2(int root){
if(dp[root] != 0)
return dp[root];
if(part[root] == 0)
return 0;
dp[root] += part[root];
int maxi = 0;
for(int i = 0; i <= 'z'-'a'; ++i){
if(edge[root][i] != 0){
if(full[edge[root][i]] > 0)
maxi = max(maxi, f2(edge[root][i]));
}
}
dp[root] += maxi;
ans = max(ans, dp[root]);
return dp[root];
}
void f1(int root){
f2(root);
for(int i = 0; i <= 'z'-'a'; ++i){
if(edge[root][i] != 0)
f1(edge[root][i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(int i = 0; i < n; ++i){
cin >> s[i];
reverse(s[i].begin(), s[i].end());
add(s[i]);
}
f1(1);
cout << ans << "\n";
}
Compilation message
rima.cpp: In function 'void add(std::__cxx11::string)':
rima.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); ++i){
~~^~~~~~~~~~
rima.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()-2 || (i == 0 && s.size() == 1))
~~^~~~~~~~~~~~~
rima.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()-1)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
15992 KB |
Output is correct |
| 2 |
Correct |
16 ms |
16120 KB |
Output is correct |
| 3 |
Correct |
16 ms |
15992 KB |
Output is correct |
| 4 |
Incorrect |
386 ms |
98044 KB |
Output isn't correct |
| 5 |
Correct |
52 ms |
22264 KB |
Output is correct |
| 6 |
Incorrect |
92 ms |
62308 KB |
Output isn't correct |
| 7 |
Incorrect |
91 ms |
61940 KB |
Output isn't correct |
| 8 |
Incorrect |
89 ms |
61740 KB |
Output isn't correct |
| 9 |
Incorrect |
117 ms |
68652 KB |
Output isn't correct |
| 10 |
Incorrect |
90 ms |
61904 KB |
Output isn't correct |
